二元樹走訪#

走訪順序記憶法#

關鍵在於根節點的訪問時機：

走訪方式	順序	記憶口訣
前序 (Preorder)	根 → 左 → 右	根在前
中序 (Inorder)	左 → 根 → 右	根在中
後序 (Postorder)	左 → 右 → 根	根在後
層序 (Level-order)	逐層從左到右	BFS

走訪範例#

假設二元樹結構：

flowchart TB
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    C --> G((G))

走訪方式	結果	說明
前序	A → B → D → E → C → F → G	根 → 左 → 右
中序	D → B → E → A → F → C → G	左 → 根 → 右
後序	D → E → B → F → G → C → A	左 → 右 → 根
層序	A → B → C → D → E → F → G	逐層從左到右

BST 的中序走訪會產生有序序列，這是面試重要考點！

層序走訪實作 (BFS)#

使用 Batch Processing 技巧區分階層：

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = collections.deque([root])

    while queue:
        level_size = len(queue)  # 鎖定當前層節點數
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

技巧：用 level_size = len(queue) 在迴圈開始時鎖定當前層數量，避免使用特殊標記。

遞迴走訪模板#

前中後序遞迴程式碼

# 前序走訪
def preorder(root):
    if not root:
        return
    print(root.val)        # 處理根
    preorder(root.left)    # 左子樹
    preorder(root.right)   # 右子樹

# 中序走訪
def inorder(root):
    if not root:
        return
    inorder(root.left)     # 左子樹
    print(root.val)        # 處理根
    inorder(root.right)    # 右子樹

# 後序走訪
def postorder(root):
    if not root:
        return
    postorder(root.left)   # 左子樹
    postorder(root.right)  # 右子樹
    print(root.val)        # 處理根

實務觀點：工作中較少區分前中後序，更常直接使用 DFS 或 BFS 的概念。學習這三種走訪主要是為了理解遞迴邏輯。