[[411457]]

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，作者程序員Carl 。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。

二叉樹的迭代遍歷

看完本篇大家可以使用迭代法，再重新解決如下三道leetcode上的題目：

• 144.二叉樹的前序遍歷
• 94.二叉樹的中序遍歷
• 145.二叉樹的后序遍歷

為什么可以用迭代法(非遞歸的方式)來實現(xiàn)二叉樹的前后中序遍歷呢?

我們在棧與隊列：匹配問題都是棧的強項中提到了，遞歸的實現(xiàn)就是：每一次遞歸調(diào)用都會把函數(shù)的局部變量、參數(shù)值和返回地址等壓入調(diào)用棧中，然后遞歸返回的時候，從棧頂彈出上一次遞歸的各項參數(shù)，所以這就是遞歸為什么可以返回上一層位置的原因。

此時大家應(yīng)該知道我們用棧也可以是實現(xiàn)二叉樹的前后中序遍歷了。

前序遍歷(迭代法)

我們先看一下前序遍歷。

前序遍歷是中左右，每次先處理的是中間節(jié)點，那么先將跟節(jié)點放入棧中，然后將右孩子加入棧，再加入左孩子。

為什么要先加入 右孩子，再加入左孩子呢?因為這樣出棧的時候才是中左右的順序。

動畫如下：

不難寫出如下代碼: (注意代碼中空節(jié)點不入棧)

class Solution { 
public: 
    vector<int> preorderTraversal(TreeNode* root) { 
        stack<TreeNode*> st; 
        vector<int> result; 
        if (root == NULL) return result; 
        st.push(root); 
        while (!st.empty()) { 
            TreeNode* node = st.top();                       // 中 
            st.pop(); 
            result.push_back(node->val); 
            if (node->right) st.push(node->right);           // 右（空節(jié)點不入棧） 
            if (node->left) st.push(node->left);             // 左（空節(jié)點不入棧） 
        } 
        return result; 
    } 
}; 

此時會發(fā)現(xiàn)貌似使用迭代法寫出前序遍歷并不難，確實不難。

此時是不是想改一點前序遍歷代碼順序就把中序遍歷搞出來了?

其實還真不行!

但接下來，再用迭代法寫中序遍歷的時候，會發(fā)現(xiàn)套路又不一樣了，目前的前序遍歷的邏輯無法直接應(yīng)用到中序遍歷上。

中序遍歷(迭代法)

為了解釋清楚，我說明一下 剛剛在迭代的過程中，其實我們有兩個操作：

處理：將元素放進result數(shù)組中

訪問：遍歷節(jié)點

分析一下為什么剛剛寫的前序遍歷的代碼，不能和中序遍歷通用呢，因為前序遍歷的順序是中左右，先訪問的元素是中間節(jié)點，要處理的元素也是中間節(jié)點，所以剛剛才能寫出相對簡潔的代碼，因為要訪問的元素和要處理的元素順序是一致的，都是中間節(jié)點。

那么再看看中序遍歷，中序遍歷是左中右，先訪問的是二叉樹頂部的節(jié)點，然后一層一層向下訪問，直到到達樹左面的最底部，再開始處理節(jié)點(也就是在把節(jié)點的數(shù)值放進result數(shù)組中)，這就造成了處理順序和訪問順序是不一致的。

那么在使用迭代法寫中序遍歷，就需要借用指針的遍歷來幫助訪問節(jié)點，棧則用來處理節(jié)點上的元素。

動畫如下：

中序遍歷，可以寫出如下代碼：

class Solution { 
public: 
    vector<int> inorderTraversal(TreeNode* root) { 
        vector<int> result; 
        stack<TreeNode*> st; 
        TreeNode* cur = root; 
        while (cur != NULL || !st.empty()) { 
            if (cur != NULL) { // 指針來訪問節(jié)點，訪問到最底層 
                st.push(cur); // 將訪問的節(jié)點放進棧 
                cur = cur->left;                // 左 
            } else { 
                cur = st.top(); // 從棧里彈出的數(shù)據(jù)，就是要處理的數(shù)據(jù)（放進result數(shù)組里的數(shù)據(jù)） 
                st.pop(); 
                result.push_back(cur->val);     // 中 
                cur = cur->right;               // 右 
            } 
        } 
        return result; 
    } 
}; 

后序遍歷(迭代法)

再來看后序遍歷，先序遍歷是中左右，后續(xù)遍歷是左右中，那么我們只需要調(diào)整一下先序遍歷的代碼順序，就變成中右左的遍歷順序，然后在反轉(zhuǎn)result數(shù)組，輸出的結(jié)果順序就是左右中了，如下圖：

所以后序遍歷只需要前序遍歷的代碼稍作修改就可以了，代碼如下：

class Solution { 
public: 
    vector<int> postorderTraversal(TreeNode* root) { 
        stack<TreeNode*> st; 
        vector<int> result; 
        if (root == NULL) return result; 
        st.push(root); 
        while (!st.empty()) { 
            TreeNode* node = st.top(); 
            st.pop(); 
            result.push_back(node->val); 
            if (node->left) st.push(node->left); // 相對于前序遍歷，這更改一下入棧順序 （空節(jié)點不入棧） 
            if (node->right) st.push(node->right); // 空節(jié)點不入棧 
        } 
        reverse(result.begin(), result.end()); // 將結(jié)果反轉(zhuǎn)之后就是左右中的順序了 
        return result; 
    } 
}; 

總結(jié)

此時我們用迭代法寫出了二叉樹的前后中序遍歷，大家可以看出前序和中序是完全兩種代碼風(fēng)格，并不想遞歸寫法那樣代碼稍做調(diào)整，就可以實現(xiàn)前后中序。

這是因為前序遍歷中訪問節(jié)點(遍歷節(jié)點)和處理節(jié)點(將元素放進result數(shù)組中)可以同步處理，但是中序就無法做到同步!

上面這句話，可能一些同學(xué)不太理解，建議自己親手用迭代法，先寫出來前序，再試試能不能寫出中序，就能理解了。

那么問題又來了，難道 二叉樹前后中序遍歷的迭代法實現(xiàn)，就不能風(fēng)格統(tǒng)一么(即前序遍歷 改變代碼順序就可以實現(xiàn)中序 和 后序)?

當然可以，這種寫法，還不是很好理解，我們將在下一篇文章里重點講解，敬請期待!

其他語言版本

Java：

// 前序遍歷順序：中-左-右，入棧順序：中-右-左 
class Solution { 
    public List<Integer> preorderTraversal(TreeNode root) { 
        List<Integer> result = new ArrayList<>(); 
        if (root == null){ 
            return result; 
        } 
        Stack<TreeNode> stack = new Stack<>(); 
        stack.push(root); 
        while (!stack.isEmpty()){ 
            TreeNode node = stack.pop(); 
            result.add(node.val); 
            if (node.right != null){ 
                stack.push(node.right); 
            } 
            if (node.left != null){ 
                stack.push(node.left); 
            } 
        } 
        return result; 
    } 
} 
 
// 中序遍歷順序: 左-中-右 入棧順序： 左-右 
class Solution { 
    public List<Integer> inorderTraversal(TreeNode root) { 
        List<Integer> result = new ArrayList<>(); 
        if (root == null){ 
            return result; 
        } 
        Stack<TreeNode> stack = new Stack<>(); 
        TreeNode cur = root; 
        while (cur != null || !stack.isEmpty()){ 
           if (cur != null){ 
               stack.push(cur); 
               cur = cur.left; 
           }else{ 
               cur = stack.pop(); 
               result.add(cur.val); 
               cur = cur.right; 
           } 
        } 
        return result; 
    } 
} 
 
// 后序遍歷順序 左-右-中 入棧順序：中-左-右 出棧順序：中-右-左， 最后翻轉(zhuǎn)結(jié)果 
class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
        List<Integer> result = new ArrayList<>(); 
        if (root == null){ 
            return result; 
        } 
        Stack<TreeNode> stack = new Stack<>(); 
        stack.push(root); 
        while (!stack.isEmpty()){ 
            TreeNode node = stack.pop(); 
            result.add(node.val); 
            if (node.left != null){ 
                stack.push(node.left); 
            } 
            if (node.right != null){ 
                stack.push(node.right); 
            } 
        } 
        Collections.reverse(result); 
        return result; 
    } 
} 

Python：

# 前序遍歷-迭代-LC144_二叉樹的前序遍歷 
class Solution: 
    def preorderTraversal(self, root: TreeNode) -> List[int]: 
        # 根結(jié)點為空則返回空列表 
        if not root: 
            return [] 
        stack = [root] 
        result = [] 
        while stack: 
            node = stack.pop() 
            # 中結(jié)點先處理 
            result.append(node.val) 
            # 右孩子先入棧 
            if node.right: 
                stack.append(node.right) 
            # 左孩子后入棧 
            if node.left: 
                stack.append(node.left) 
        return result 
         
# 中序遍歷-迭代-LC94_二叉樹的中序遍歷 
class Solution: 
    def inorderTraversal(self, root: TreeNode) -> List[int]: 
        if not root: 
            return [] 
        stack = []  # 不能提前將root結(jié)點加入stack中 
        result = [] 
        cur = root 
        while cur or stack: 
            # 先迭代訪問最底層的左子樹結(jié)點 
            if cur:      
                stack.append(cur) 
                cur = cur.left   
            # 到達最左結(jié)點后處理棧頂結(jié)點     
            else:   
                cur = stack.pop() 
                result.append(cur.val) 
                # 取棧頂元素右結(jié)點 
                cur = cur.right  
        return result 
         
# 后序遍歷-迭代-LC145_二叉樹的后序遍歷 
class Solution: 
    def postorderTraversal(self, root: TreeNode) -> List[int]: 
        if not root: 
            return [] 
        stack = [root] 
        result = [] 
        while stack: 
            node = stack.pop() 
            # 中結(jié)點先處理 
            result.append(node.val) 
            # 左孩子先入棧 
            if node.left: 
                stack.append(node.left) 
            # 右孩子后入棧 
            if node.right: 
                stack.append(node.right) 
        # 將最終的數(shù)組翻轉(zhuǎn) 
        return result[::-1]