[[423968]]

刷Leetcode，需要知道一定的算法模板，本次先總結(jié)下二叉樹的遞歸和非遞歸的遍歷算法模板。

二叉樹的四種遍歷方式，前中后加上層序遍歷。對(duì)于二叉樹的前中后層序遍歷，每種遍歷都可以遞歸和循環(huán)兩種實(shí)現(xiàn)方法，且每種遍歷的遞歸實(shí)現(xiàn)都比循環(huán)實(shí)現(xiàn)要簡(jiǎn)潔。下面做一個(gè)小結(jié)，看了《代碼隨想錄》哈工大大佬的刷題指南，深受啟發(fā)，因，下面代碼有一定來(lái)源《代碼隨想錄》。

遞歸

下面?zhèn)未a是二叉樹遍歷的遞歸算法模板，順序是中左右，也就是前序遍歷，改變中左右三行代碼的順序，前中后序三種遞歸遍歷輕松解決。

def preorderTraversal(root: TreeNode) -> List[int]: 
    res = [] 
    def help(root): 
        if not root: return 
        res.append(root.val) # 中 
        help(root.left) # 左 
        help(root.right) # 右 
    help(root) 
    return res 

對(duì)此也提供C++代碼，遞歸算法模板一定要加上終止條件，不然一入遞歸深似海，從此offer是路人，來(lái)源代碼隨想錄。

void help(TreeNode * root , vector<int> &res) { 
    if (root == nullptr) { 
        return; 
    } 
    res.push_back(root->val); // 中 
    help(root->left,res); // 左 
    help(root->right,res); //右 
} 
 
 
vector<int> preorderTraversal(TreeNode* root) { 
    vector<int> res; 
    help(root,res); 
    return res; 
} 

迭代

迭代遍歷二叉樹的比遞歸難度加大，其實(shí)使用了一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)，《代碼隨想錄》非常巧妙的使用空指針來(lái)作標(biāo)記，原理是將處理的節(jié)點(diǎn)放入棧之后，緊接著放入一個(gè)空指針作為標(biāo)記。

由于棧是先進(jìn)后出，所以前序遍歷的順序中左右，在加到棧中，需要反過(guò)來(lái)進(jìn)行添加，每添加一個(gè)元素在后面添加一個(gè)空指針，在Python中也可以使用None來(lái)代替。

下面是具體的偽代碼，至于中序和后序遍歷，改下向棧中添加節(jié)點(diǎn)的順序即可。

def preorderTraversal(root: TreeNode) -> List[int]: 
      result = [] 
      st= [] 
      # 1、判斷root 
      if root: 
          st.append(root) 
      while st: 
          node = st.pop() 
          if node != None: 
              # 右左中 添加到棧中，然后中左右拿出 
              if node.right: #右 
                  st.append(node.right) 
              if node.left: #左 
                  st.append(node.left) 
              st.append(node) #中 
              # 添加一個(gè)空指針 記錄節(jié)點(diǎn) 
              st.append(None) 
          else:  
             # node是空指針，那么下一個(gè)就是加入的節(jié)點(diǎn) 
              node = st.pop() 
              result.append(node.val) 
      return result 

下面是具體的C++代碼，由于C++中的stack中pop之后，沒(méi)有返回值，因此需要額外注意。

vector<int> preorderTraversal(TreeNode* root) { 
        vector<int>res; 
        stack<TreeNode*> st; 
        if (root != nullptr) st.push(root); 
        while(!st.empty()){ 
            TreeNode* node = st.top(); 
            if(node != nullptr){ 
                st.pop(); 
                if(node->right) st.push(node->right); 
                if (node->left) st.push(node->left); 
                st.push(node); 
                st.push(NULL); 
            }else{ 
                // 需要額外注意下 
                st.pop(); 
                node = st.top(); 
                st.pop(); 
                res.push_back(node->val); 
            } 
        } 
        return res; 
     
    } 

層次遍歷

其實(shí)，樹的遍歷也分為兩種，分別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷。關(guān)于樹的不同深度優(yōu)先遍歷(前序，中序和后序遍歷)就是遞歸和非遞歸的寫法。廣度優(yōu)先遍歷在樹中，就是層次遍歷。

在二叉樹的層級(jí)遍歷中，我們需要用到隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，幫助我們完成遍歷。

在Python偽代碼中，

def levelOrder(root: TreeNode) -> List[List[int]]: 
 # 1、判斷root 
   if not root: 
        return [] 
    # 把root添加到quene 中 
    quene = [root] 
    out_list = [] 
    while quene: 
     # while 第一步就是求length  
        length = len(queue)   
        in_list = [] 
        for _ in range(length): 
         # 在C++中，這里需要兩行 
            curnode = queue.pop(0)  # （默認(rèn)移除列表最后一個(gè)元素）這里需要移除隊(duì)列最頭上的那個(gè) 
            in_list.append(curnode.val) 
            if curnode.left: queue.append(curnode.left) 
            if curnode.right: queue.append(curnode.right) 
        out_list.append(in_list) 
    return out_list 

通過(guò)上面的Python偽代碼，進(jìn)行書寫更高效的C++代碼。

class Solution { 
public: 
    vector<vector<int>> levelOrder(TreeNode* root) { 
        vector<vector<int>> res; 
        queue<TreeNode*> que; 
        // 判斷  root 
        if (root != nullptr) que.push(root); 
        while(!que.empty()) { 
             // 開(kāi)始先求隊(duì)列的長(zhǎng)度 
            int size = que.size(); 
            vector<int> vec; 
            // 迭代添加節(jié)點(diǎn)元素 
            for (int i = 0 ; i<size; i++){ 
                TreeNode* node = que.front(); 
                que.pop(); 
                vec.push_back(node->val); 
                if (node->left) que.push(node->left); 
                if (node->right) que.push(node->right); 
            } 
            res.push_back(vec); 
        } 
        return res; 
    } 
}; 

上述為樹的遍歷模板。其實(shí)本質(zhì)上也是深度優(yōu)先遍歷與廣度優(yōu)先遍歷的算法模板，許多其它操作都是建立在樹遍歷操作的基礎(chǔ)之上，因此掌握樹的所有遍歷方法，等于解決了一半樹的題目。