二叉树以根节点的位置不同，定义了3种遍历方式。
1、先序遍历：根节点在开始位置，根节点、左节点、右节点。《栈》
2、中序遍历：根节点在中间位置，左节点、根节点、右节点。《栈》
3、后序遍历：根节点在最后位置，左节点、右节点、根节点。《栈》
其他遍历
4、层次遍历：以根节点为第一层，一层层遍历。《队列》

遍历二叉树是理解递归的重要方法，二叉树是一种最简单的自相似树，反复重复自己形成的树。除了用递归的写法，还有用栈的写法也要掌握，因为，用栈的写法详细的解释了，递归的工作原理。递归就是系统使用一个隐藏的栈辅助。用栈的写法可以详细的了解递归内部的运作原理，更加清晰明了递归的运行原理。

无论递归还是迭代，每个节点都是作为当前根节点来处理的。所以在函数代码中只有一次push_back

root=root->right 迭代写法中这循环中的最后一句，相当于递归传参 digui(root->right)

先序遍历

递归写法

class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == NULL) return;//如果root空就退出
        res.push_back(root->val);//把root放入res
        preorder(root->left, res);//递归左节点
        preorder(root->right, res);//递归右节点
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;//定义返回容器res
        preorder(root, res);//递归
        return res;//返回
    }
};

栈写法

栈顶节点就是我们需要的最近的父节点。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;//定义容器
        if (root == NULL) return res;//root空就返回
        stack<TreeNode*> stk;//定义栈容器
//root写前面，可省略第5行
        while (root!=NULL || !stk.empty()) {//root不空或stk不空就循环
            while (root != NULL) {//root不空循环
                res.push_back(root->val);//把root的值放入res
                stk.push(root);//把root节点放入栈中
                root = root->left;//移动到左节点
            }
            root = stk.top();//栈顶节点存入root，栈顶就是最近的父节点
            stk.pop();//弹出栈顶节点
            root = root->right;//移动到右节点
        }
        return res;//返回
    }
};

中序遍历

递归写法

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (root==NULL) return;//root空就退出
        inorder(root->left, res);//移动到左节点
        res.push_back(root->val);//把当前值放入res
        inorder(root->right, res);//移动到右节点
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};
//当前节点的下一层某个分叉执行完毕后，会返回到上一层执行剩余没有执行的分叉上去执行。

栈写法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;//定义返回容器res
        if(root==NULL) return res;//若root空返回res，注意这句可省略
        stack<TreeNode*> stk;//定义栈
        while (root != NULL || !stk.empty()) {//若root不空或stk不空就循环
            while (root != NULL) {//root不空就循环
                stk.push(root);//放入栈
                root = root->left;//移动到左节点
            }
            root = stk.top();//取出栈顶节点放入root
            stk.pop();//弹出栈顶节点
            res.push_back(root->val);//放入节点值到res
            root = root->right;//移动到右节点
        }
        return res;//返回
    }
};

后序遍历

递归写法

class Solution {
public:
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == NULL) return;//root空就退出
        postorder(root->left, res);//移动到左节点
        postorder(root->right, res);//移动到右节点
        res.push_back(root->val);//当前节点的值放入res
    }
    //当前子节点执行完毕后，返回到父节点执行剩余的子节点。

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
};

栈写法

//后序遍历中，每个根会被访问2次，第一次时右节点是新点，访问右节点。
//第2次时，右节点是旧点，就访问根。
//访问方法是：先尽可能的访问最左侧的左节点，然后通过根访问右节点，再从右节点回到根节点。
//放：放入容器，存：存入变量
class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            vector<int> res;//定义存储容器
            if (root == NULL) return res;//如果root为空，返回res，这句可以省略
            stack<TreeNode*> stk;//定义栈
            TreeNode *prev = NULL;//存放上一个访问的节点
            while (root != NULL || !stk.empty()) {//如果root不空或stk不空就循环
                while (root != NULL) {//如果root不空循环
                    stk.push(root);//把root放入stk
                    root = root->left;//移动到左节点
                }//root为空时退出循环
                root = stk.top();//把栈顶的节点存入root
                stk.pop();//弹出栈顶
                if (root->right == NULL || root->right == prev) {//访问根时需要执行的代码
                    res.push_back(root->val);//把root放入res
                    prev = root;//把当前点存入prev作为父节点的标记
                    root = NULL;//把root置空，第2个while循环不必执行
                } else {//访问右节点需要执行的代码
                    stk.push(root);
                    root = root->right;
                }
            }
            return res;//返回res
        }
};

层次遍历《使用队列》

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int> > res;
        if (root==NULL) return res;//如果root空则返回
        queue <TreeNode*> q;//定义队列
        q.push(root);//把第一个放入队列
        while (!q.empty()) {//队列不空就循环
            int n = q.size();//获取当前层的大小
            res.push_back(vector <int> ());//放入一个空的vector
            for (int i = 0; i < n; i++) {//处理当前层的节点
                TreeNode *node = q.front(); q.pop();//队列头存入node，弹出头
                res.back().push_back(node->val);//把当前节点放入res
                if (node->left!=NULL) q.push(node->left);//如果左端点不空，则移动到左端点
                if (node->right!=NULL) q.push(node->right);//如果右端点不空，则移动到右端点
            }
        }

        return res;//返回
    }
};