二叉樹：二叉樹的三種遍歷方式，遞歸實現超簡單

二叉樹是一種非常基礎的數據結構，每個節點最多有兩個子節點（左子樹和右子樹）。遍歷二叉樹就是按照特定順序訪問每個節點，就像逛超市時按順序逛貨架一樣。今天我們要學的是二叉樹最經典的三種遍歷方式：前序、中序、後序，而且用遞歸實現，簡單易懂！

先搞懂：什麼是遞歸？¶

遞歸就像“套娃”——函數自己調用自己，但每次處理的“範圍”更小，直到遇到終止條件（比如“套”到空盒子就停止）。舉個例子：你要計算1+2+3+…+n，遞歸的思路是先算1+2+…+(n-1)，再加上n。

二叉樹的三種遍歷順序¶

遍歷順序的關鍵是“根節點”的訪問位置，三種方式分別是：
- 前序遍歷：根 → 左子樹 → 右子樹（先看根，再逛左貨架，最後逛右貨架）
- 中序遍歷：左子樹 → 根 → 右子樹（先逛左貨架，再看根，最後逛右貨架）
- 後序遍歷：左子樹 → 右子樹 → 根（先逛左、右貨架，最後看根）

用例子理解遍歷過程¶

我們用一個具體的二叉樹舉例，方便直觀感受：

    1
   / \
  2   3
 / \
4   5

這個樹的結構是：根節點是1，左子樹的根是2，右子樹的根是3；2的左孩子是4，右孩子是5。

1. 前序遍歷（根左右）¶

順序：先訪問根節點，再遍歷左子樹，最後遍歷右子樹。

遞歸實現：¶

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

def preorder(root):
    if root is None:  # 終止條件：空節點直接返回
        return
    print(root.val, end=" ")  # 訪問根節點
    preorder(root.left)       # 遞歸左子樹
    preorder(root.right)      # 遞歸右子樹

遍歷過程（以上面的樹爲例）：¶

• 從根節點1開始，打印1 → 進入左子樹（節點2）
• 打印2 → 進入左子樹（節點4）
• 節點4沒有子節點，打印4 → 返回上一層
• 回到節點2，進入右子樹（節點5），打印5 → 返回上一層
• 回到根節點1，進入右子樹（節點3），打印3 → 結束

遍歷結果：1 2 4 5 3

2. 中序遍歷（左根右）¶

順序：先遍歷左子樹，再訪問根節點，最後遍歷右子樹。

遞歸實現：¶

def inorder(root):
    if root is None:
        return
    inorder(root.left)        # 遞歸左子樹
    print(root.val, end=" ")  # 訪問根節點
    inorder(root.right)       # 遞歸右子樹

遍歷過程：¶

• 遞歸到左子樹最深處（節點4），打印4 → 返回
• 回到節點2，打印2 → 進入右子樹（節點5），打印5 → 返回
• 回到根節點1，打印1 → 進入右子樹（節點3），打印3 → 結束

遍歷結果：4 2 5 1 3

3. 後序遍歷（左右根）¶

順序：先遍歷左子樹，再遍歷右子樹，最後訪問根節點。

遞歸實現：¶

def postorder(root):
    if root is None:
        return
    postorder(root.left)      # 遞歸左子樹
    postorder(root.right)     # 遞歸右子樹
    print(root.val, end=" ")  # 訪問根節點

遍歷過程：¶

• 遞歸到左子樹最深處（節點4），打印4 → 返回
• 遞歸到節點5，打印5 → 返回
• 回到節點2，打印2 → 遞歸右子樹（節點3），打印3 → 返回
• 回到根節點1，打印1 → 結束

遍歷結果：4 5 2 3 1

三種遍歷的核心區別¶

遞歸的關鍵思想¶

1. 終止條件：噹噹前節點爲空（root is None）時，直接返回，不再遞歸。
2. 遞歸邏輯：根據遍歷順序，先處理當前節點（根），再遞歸左右子樹（順序不同，處理順序不同）。
3. “自頂向下”的執行：從根節點開始，逐步深入到葉子節點，再回溯處理上層節點。

通過遞歸實現三種遍歷，你會發現核心是“明確順序，遞歸調用”。只要記住每種遍歷的“根位置”，就能輕鬆寫出遞歸函數。多動手畫一畫樹的結構，跟着遞歸過程走一遍，很快就能掌握啦！