相信只要了解過(guò)二叉樹(shù)，都知道二叉樹(shù)的3種遍歷方式：前序遍歷、中序遍歷、后序遍歷。
甚至不夸張的說(shuō)，其遞歸的遍歷方法閉著眼睛也能寫(xiě)出來(lái)。所以本篇意不在記錄其遞歸的寫(xiě)法，而是探尋其迭代的方法。

0、定義二叉樹(shù)

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

1. 前序遍歷

想要理解或者實(shí)現(xiàn)前序遍歷方法，我們可以從其遞歸方法入手，了解其實(shí)現(xiàn)過(guò)程。

class Solution:
    def preorderTraversal(self, root: TreeNode):
        res = []
        
        def dfs(root):
            nonlocal res
            if not root:
                return 
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        
        dfs(root)
        return res

將其遞歸的過(guò)程展開(kāi)，就如同其下的方式：訪問(wèn)當(dāng)前節(jié)點(diǎn)，進(jìn)入左子節(jié)點(diǎn)，然后訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)……，遇到null則返回，然后訪問(wèn)節(jié)點(diǎn)的右子節(jié)點(diǎn)，由于節(jié)點(diǎn)不能反向找到其父節(jié)點(diǎn)，我們需要保存其右子節(jié)點(diǎn)。同時(shí)，我們需要從最近的右子節(jié)點(diǎn)開(kāi)始訪問(wèn)，也即利用棧來(lái)代替遞歸算法中的調(diào)用棧。

dfs(root)
    print(root.val)
    dfs(root.left)
        print(root.left.val)
        dfs(root.left)
            null return
        dfs(root.right)
            print(root.right.val)
            dfs(root.left)
            ...

下面是其迭代方法的實(shí)現(xiàn)

class Solution:
    def preorderTraversal(self, root):
        res = []
        stack = []
        
        while stack or root:
            while root:
                res.append(root.val)
                stack.append(root.right)
                root = root.left
            root = stack.pop()
        
        return res

2. 中序遍歷

中序遍歷的遞歸調(diào)用過(guò)程如下，深入左子節(jié)點(diǎn)，當(dāng)其為空則返回，訪問(wèn)節(jié)點(diǎn)，然后進(jìn)入其右子節(jié)點(diǎn)。重復(fù)該過(guò)程。

dfs(root)
    dfs(root.left)
        dfs(root.left)
            null return
        print(root.val)
        dfs(root.right)
            dfs(root.left)
                dfs(root.left)
                ...

可以看到，我們需要先將左子節(jié)點(diǎn)保存，待其為空后，當(dāng)問(wèn)節(jié)點(diǎn)，進(jìn)入右子樹(shù)，繼續(xù)……

class Solution:
    def inorderTraversal(self, root: TreeNode):
        res = []
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res

3. 后序遍歷

后序遍歷可以看著是前序遍歷的鏡像，所以可以套用前序遍歷的方法，但是需要將最后結(jié)果進(jìn)行反轉(zhuǎn)。

class Solution:
    def postorderTraversal(self, root):
        res = []
        stack = []
        
        while stack or root:
            while root:
                res.append(root.val)
                stack.append(root.left)
                root = root.right
            root = stack.pop()
        
        return res[::-1]

4. 顏色標(biāo)記法

這個(gè)方法是leetcode解題中，針對(duì)前中后序遍歷均適用，而且容易理解。
以后序遍歷為例，其代碼如下。需要注意的是，因?yàn)闂５暮筮M(jìn)先出結(jié)構(gòu)，所以我們的入棧順序?yàn)橄喾捶较颉?br> 同理，如果是前序遍歷，則入棧順序?yàn)椋河?、左、中?br> 中序遍歷的入棧順序?yàn)椋河?、中、左?/p>

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        white, gray = 1, 0
        stack = [(white, root)]
        while stack:
            color, node = stack.pop()
            if not node:
                continue
            if color == white:
                stack.append((gray, node))
                stack.append((white, node.right))
                stack.append((white, node.left))
            else:
                res.append(node.val)
        return res

5. leetcode

94. 二叉樹(shù)的中序遍歷

145. 二叉樹(shù)的后序遍歷

6. 參考

1、https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
2、https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/die-dai-fa-by-jason-2/