哈嘍大家，這里是小餅干，面向就業編程，持續更新學習路徑，歡迎關注點贊鴨

這周開始刷二叉樹了，一上來就是4種二叉樹遍歷，發現之前自己會了但沒有完全會= =，

二叉樹的遍歷可以分為：

（一）二叉樹的深度優先遍歷：
①前序遍歷
②中序遍歷
③后序遍歷

（二）二叉樹的廣度優先遍歷：
層序遍歷

遞回寫法看不懂的可以先看看這個：
Leetcode代碼隨想錄題解
代碼隨想錄

遞回寫法都挺簡單，算是easy題，迭代就好難QAQ,medium或者hard,寫法還五花八門的，
有人說會了遞回法就行了，能寫出來就行，如果不懂迭代法，你真的懂了遞回的程序了嘛？迭代就是對遞回細節化的拆分，
還有見迭代法寫的完全沒迭代的味兒，遍歷”的本質是對記憶體的有序訪問，失去了訪問順序，即便用各種資料結構恢復了這個次序，遍歷本身也顯得毫無意義,有人把前序遍歷左右入堆疊順序改了，最后結果reverse一下就成后序遍歷了，雖然結果對了，但還是感覺很別扭，這篇主要講講怎么用迭代法進行遍歷，
只有當各個節點以“左->右->中”的次序依次出現在迭代的loop當中時，它才是真正的后序遍歷，Leetcode官解就很可，咱就直接拿官解寫法講了，

前中后序遍歷的本質還是深度優先遍歷，所以要用到堆疊，用來保存當前走過的節點的路徑，其后進先出的特性可以幫助我們遍歷完當前節點及其子節點后回傳上一節點，

具體的解釋都寫在代碼里了，

1.Leectcode144. 二叉樹的前序遍歷

法一：遞回

class Solution {
public:
    vector<int>ans;
    vector<int> preorderTraversal(TreeNode* root) {    
        preorder(root);
        return ans;
    }
    void preorder(TreeNode *root){
        if(root==NULL)return ;
        ans.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    }
};

法二：迭代

class Solution {
public:
    
    vector<int> preorderTraversal(TreeNode* root) {  
       vector<int>ans;  
       stack<TreeNode*>st;
       //用來表示當前遍歷到的節點
       TreeNode *node=root;
       
//為什么回圈會有兩個條件呢？不著急，我們先往下看
       while(!st.empty()||node){
       //前序遍歷順序為中左右，即根結點->根結點的左子樹的根結點->根結點的左子樹的的根結點的左子樹的根結點->...開始套娃->根結點的右子樹的根結點
       //所以我們先一直向左走，并記錄路徑上的節點，先中間節點所以可以把當前子樹的根結點的值加到ans了
           while(node){
               st.push(node);
               ans.push_back(node->val);
               node=node->left;
           }
           //當node=NULL時，此時找到最左的葉節點，即最左子樹的左孩子節點
           //左邊遍歷完了，我們就可以回到上一層，找到最左子樹的根結點，根節點其實已經遍歷過了，我們這里只是想退回一步
           node=st.top();
           //就差最左子樹的右孩子節點了，右孩子節點為NULL就直接到上一層了，不為空就接著遍歷一下，所以堆疊最左子樹的根結點可以彈出了
           st.pop();
           //遍歷最左子樹的右節點
           node=node->right;
           //右節點為NULL就直接到上一層了，node=st.top(),不為空就接著遍歷右子樹，找到最左，就像對根結點開始的操作一樣，但其實我們對左子樹的操作也是這樣，只是因為第一步是向左走的，所以不容易發現QVQ
       }
//又回到一開始的問題，為什么回圈會有兩個條件呢？
//（一）!st.empty()這個很好理解，就是堆疊里還有保存的上一層的根節點，所以要回接著遍歷它們的右子樹，是向上的
//（二）node!=NULL 說明當前node非空，需要對當前節點做下一步操作，是向下的

       return ans;
    }
    
    
};

現在大家可以自己試著理解下中序和后序代碼了

2. Leectcode94. 二叉樹的中序遍歷

法一：遞回

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

    }
};

法二：迭代

class Solution {
public:
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        stack<TreeNode *>st;
        TreeNode *node=root;
        while(!st.empty()||node){
            while(node){
                st.push(node);
                //這里中序遍歷先左后中，所以ans沒有記錄中間節點的值
                node=node->left;
            }
            node=st.top(); 
            st.pop();
            ans.push_back(node->val);     
            node=node->right;
        }
        return ans;
    }
    
};

3.Leectcode145. 二叉樹的后序遍歷

法一：遞回

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

法二：迭代

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode *> stk;
        TreeNode *node=root;
        TreeNode *prev = nullptr;
        while (node != nullptr || !stk.empty()) {
            while (node != nullptr) {
                stk.push(node);
                node = node->left;
            }
            //左孩子結點為空，回到父結點
            node = stk.top();
            stk.pop();
            //很多人可能會問，這里怎么變了？pre又是什么？
            //這里其實跟之前是一樣的，root->right == prev，說明右孩子節點已經遍歷過了，這回是最后遍歷中間節點，所以要先遍歷完右子樹
            //右孩子為空/右子樹遍歷過了，ans就可以加入根結點值了
            if (node->right == nullptr || node->right == prev) {
                res.push_back(node->val);
                prev = node;
                node = nullptr;
            } else {
                stk.push(node);
                node = node->right;
            }
        }
        return res;
    }
};

下面看看層序遍歷，層序遍歷的本質還是廣度優先遍歷，所以要用到佇列，用來保存當前走過的節點的路徑，其先進先出的特性可以幫助我們遍歷完當前層節點再繼續按順序按順序遍歷下一層子節點，

4.Leetcode102.二叉樹的層序遍歷

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) { 
          vector<vector<int>>ans;
          if(root==NULL)return ans;
          queue<TreeNode*>q;
          q.push(root);
          while(!q.empty()){
              //當前佇列元素個數恰好等于當前層元素個數
              int len=q.size();
              vector<int>level;
              for(int i=0;i<len;i++){
                  auto t=q.front(); 
                  q.pop();
                  level.push_back(t->val);
                  if(t->left)q.push(t->left);
                  if(t->right)q.push(t->right);
              }
              ans.push_back(level);
              
          }
          return ans;
    }
};

還沒有看懂的小伙伴可能是還不太理解遍歷程序，可以先看看官解的動態圖，再回來看代碼，最后記得自己多寫幾遍哈