解惑药水：二叉树的前序，中序，后序，层序遍历实现

二叉树的先序遍历

先序遍历就是按照遍历规则：根、左、右

如图，该二叉树的遍历顺序为：

首先看根节点1，它没有左子树，所以先访问1，然后访问它的右子树2；
节点2有左子树3，右子树4，所以先访问节点2，然后3，然后4；
节点3没有左子树，所以先访问节点3，然后右子树5；
节点5没有右子树，所以先访问节点5，然后左子树6；至此根节点左子树访问完毕；接着访问根节点的右子树4
先访问节点4，然后左子树7，右子树8；
因此，总的节点访问顺序就是：1,2,3,5,6,4,7,8

然后我们考虑如何实现二叉树的前序遍历？
其实就是递归的思想

class Solution {
   
public:
 void preorder(TreeNode *root, vector<int> &res) {
   
        if (root == nullptr) {
   
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode* root) {
   
         vector<int> res;
         preorder(root,res);
         return res;
    }
};

二叉树的中序遍历

中序遍历就是更改了一下访问的规则：左、根、右

还是这个图：

对于根节点1，没有左子树，所以访问顺序就是先1，后2；
访问顺序：1,（以2为根节点的中序遍历顺序）
以n为根节点的中序遍历顺序：后面简称为（n）
对于节点2来说，应该是先3，然后2，然后4；
访问顺序：1,(3),2,(4)
对于3来说，没有左子树，所以就是先3，后5；
访问顺序：1,3,(5),2,(4)
对于5来说，先6，后5；
访问顺序：1,3,(6),5,2,(4)
对于6来说，没有左右子树，直接访问6；
访问顺序：1,3,6,5,2,(4)
对于4来说，先7，然后4，然后8；
访问顺序：1,3,6,5,2,(7),4,(8)
对于7来说，没有左右子树，直接访问7；
访问顺序：1,3,6,5,2,7,4,(8)
对于8来说，没有左右子树，直接访问8；
访问顺序：1,3,6,5,2,7,4,8
最终的访问顺序就是：1,3,6,5,2,7,4,8

中序遍历的实现与前序遍历相比较，就是访问顺序变了，同样也是用递归实现，只需要先访问左子树，然后根节点，然后右子树；体现在遍历上，就是先输出左子树的val，然后根节点的val，最后右子树的val；

class Solution {
   
public:
    void inorder(TreeNode* root,vector<int>&  res)
    {
   
        if(root==nullptr)
            return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
   
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

二叉树的后序遍历

后序遍历的访问规则：左、右、根
以n为根节点的后序遍历顺序：后面简称为（n）

对于节点1，没有左子树，所以先访问右子树2，然后根节点；
访问顺序：(2),1
对于节点2来说，先3，然后4，最后2
访问顺序：(3),(4),2,1
对于3来讲，没有左子树，先5，后3
访问顺序：(5),3,(4),2,1
对于5来讲，没有右子树，先6，后5
访问顺序：(6),5,3,(4),2,1
对于6来讲，直接6
访问顺序：6,5,3,(4),2,1
对于4来讲，先7后8然后4
访问顺序：6,5,3,(7),(8),4,2,1
对于7来讲，直接7
访问顺序：6,5,3,7,(8),4,2,1
对于8来讲，直接8
访问顺序：6,5,3,7,8,4,2,1
最终的访问顺序就是：6,5,3,7,8,4,2,1

class Solution {
   
public:
    void postorder(TreeNode* root,vector<int>& res)
    {
   
        if(root==nullptr)
            return;
        postorder(root->left,res);
        postorder(root->right,res); 
        res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
   
        vector<int> res;
        postorder(root,res);
        return res;
    }
};

二叉树的层序遍历

层序遍历：简言之就是一层一层的遍历
对于上面的二叉树，访问顺序就为：
[1]
[2]
[3,4]
[5,7,8]
[6]
合起来就是[1,2,3,4,5,7,8,6]
层序遍历就是BFS思想（广度优先搜索）实际体现。BFS一般使用队列queue来实现，具体来说，就是：
定义一个队列 queue<TreeNode*> MyQue;

首先，根节点入队 [1]
根节点出队，左子树，右子树入队 [2]
2出队，3,4，入队 [3,4]
3出队，5入队[4,5]
4出队，7,8，入队[5,7,8]
5出队，6入队[7,8,6]
7出队[8,6]
8出队[6]
6出队[]

归纳一下，可以按照层数来分：

根节点1入队；

根节点1出队，节点2入队；

节点2出队，节点3,4入队；

节点3出队，5入队；节点4出队，节点7,8入队；

节点5出队，节点6入队；节点7出队；节点8出队

节点6出队；

class Solution {
   
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
   
        //层序遍历：1. 哈希表 2.队列 3.递归
        //队列Queue，先进先出，Queue的size就是当前层的元素个数 
        if(root==NULL) return {
   };
        queue<TreeNode*> MyQue;
        MyQue.push(root);
        vector<vector<int>> Res;
        while(!MyQue.empty()){
   
            int size=MyQue.size(); 
            vector<int> res;
            for(int i=0;i<size;++i){
   
                TreeNode* tmp=MyQue.front();
                MyQue.pop();
                res.push_back(tmp->val);
                if(tmp->left!=NULL) MyQue.push(tmp->left);
                if(tmp->right!=NULL) MyQue.push(tmp->right);
            }
            Res.push_back(res);
        }
        return Res;
    }
};