二叉樹的周遊-----遞歸和疊代模闆總結~超簡單。

先序: 左右根

中序: 左根右

後序: 左右根

先說遞歸：

先序:

def preTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            res.append(root.val) # 通路根節點
            dfs(root.left)    # 遞歸左
            dfs(root.right)    # 遞歸右
    dfs(root)
    return      

中序:

def inorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            dfs(root.left)
            res.append(root.val)
            dfs(root.right)
    dfs(root)
    return      

後序:

def laterTraversal(self, root: TreeNode) -> List[int]:
    res = []
    def dfs(root):
        if root:
            dfs(root.left)
            dfs(root.right)
            res.append(root.val)
    dfs(root)
    return      

疊代:

先序:

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        res, stack = [], []
        while root or stack: # stack為空且node為null時，說明周遊結束
            while root: # 可以進入左子樹時，先通路，再進入
                res.append(root.val)
                stack.append(root)
                root = root.left
            root = stack.pop()
            root = root.right # 否則進入棧中節點的右子樹
        return      

中序:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:

        if not root: return []  # 若root為空則直接傳回空
        res, stack = [], []
        while root or stack: # stack為空且root為null時，說明已經周遊結束
            while root: # 可以深入左子樹
                stack.append(root)
                root = root.left
            root = stack.pop() # 否則通路棧中節點，并深入右子樹
            res.append(root.val)
            root = root.right
        return      

後序:

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        res, stack = [], []
        prev = None
        # prev記錄剛剛通路的節點，
        # 如果目前通路節點是上次通路節點的父節點，則說明子樹通路完成，可以通路目前節點了。
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 比前序和中序的模闆增加一個判斷過程：節點沒有右孩子或已經通路了該節點的子節點
            if not root.right or root.right == prev:
                res.append(root.val)
                prev = root
                root = None     # 這裡root必須要重新設定成None
                                # 因為走到這一步的時候，左右都已經是空的了。
                                # 預防再次循環的時候root進入到一開始的那個while
            else: # 存在右孩子沒周遊
                stack.append(root)
                root = root.right
        return      

後序稍微加了一個判斷子產品。畫個樹，手動模拟一下就了解了。

注釋都寫在代碼裡了，看一下就懂了~

另外兩中方法的時間複雜度.

遞歸的

疊代的