94. Binary Tree Inorder Traversal

──────────────────────────────────────────────────────────────────────

中序遍歷：先走左子樹，再處理自己，最後走右子樹。

思路

三種深度優先遍歷的差別只有「處理自己」那一行放在哪，所以遞迴版三題等於一題。LeetCode 在這題的 follow-up 一樣是：

Recursive solution is trivial, could you do it iteratively?

中序的 iterative 版是三種裡最經典的一個，因為它示範了「用棧模擬遞迴」的核心動作：一路往左走到底，沿途把節點壓進棧裡。壓進去的每個節點都代表一件待辦事項 ——「我等你的左子樹走完再處理你」。

為什麼中序特別重要

前序和後序都是「順序不同的走法」，但中序在 BST 上有一個特權：

BST 的中序遍歷結果一定是遞增序列。

這句話是一整批題目的鑰匙。看到 BST 就先想中序，然後題目就退化成「在一個排序陣列上做事」：

驗證是不是 BST → 中序序列是否嚴格遞增（98）
找第 k 小 → 中序走到第 k 個就回傳（230）
找出被交換的兩個節點 → 中序序列裡的兩個逆序對（99）
轉成排序的雙向鏈結串列 → 中序 + 一路接指標（426）

所以這題不只是「練遍歷」，它是 BST 那一整組題的前置。整理見 Tree 遍歷模板。

解題方向

遞迴

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        res.extend(self.inorderTraversal(root.left))
        res.append(root.val)
        res.extend(self.inorderTraversal(root.right))
        return res

「答案 = 左子樹的答案 + 自己 + 右子樹的答案」，直接對應定義，很好讀。但每一層都在複製子樹回傳的整個 list，複雜度會退化 —— 見下面的複雜度分析。

共用一個 res 的版本是嚴格 $O (n)$ ，也是實戰要用的形狀（因為往往要在遍歷途中做事，而不是把整個 list 拼出來）：

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

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            res.append(node.val)      # 中序：處理自己夾在中間
            dfs(node.right)

        dfs(root)
        return res

Iterative

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

        while cur or stack:
            while cur:                 # 一路往左，沿途壓棧
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()          # 最左邊還沒處理的節點
            res.append(cur.val)
            cur = cur.right            # 換到右子樹，重複同樣的事

        return res

三個容易卡住的地方：

迴圈條件是 while cur or stack，兩個都要。cur 有東西表示還有子樹沒下潛；棧裡有東西表示還有節點等著被處理。只寫一個會提早結束。
stack.pop() 出來的節點，它的左子樹保證已經走完了 —— 因為它是在「一路往左」的過程中被壓進去的，比它更左的節點都在它上面，會先被彈出。
處理完之後 cur = cur.right，不需要顯式回到父節點：父節點已經在棧裡等著了。

這個 while cur: 往左壓棧 的骨架就是「用棧模擬遞迴」的標準寫法，173. Binary Search Tree Iterator 就是把它拆成 next() / hasNext() 兩個方法，本質完全一樣。

補充

四種遍歷一起看：144. 前序（iterative 最單純）、94. 中序、145. 後序（iterative 最麻煩）、102. 層序（唯一用佇列）。

把中序當成工具的題目：98. Validate Binary Search Tree、230. Kth Smallest Element in a BST、173. Binary Search Tree Iterator。

複雜度

遞迴（extend 版）

時間 $O (n \log n)$ ~ $O (n^{2})$ — 每一層都複製子樹的 list；平衡樹是 $O (n \log n)$ ，斜樹退化成 $O (n^{2})$
空間 $O (n)$ — 遞迴堆疊加上中途產生的暫時 list

遞迴（共用 res 版）

時間 $O (n)$ — 每個節點只 append 一次
空間 $O (h)$ — 只有遞迴堆疊

Iterative

時間 $O (n)$ — 每個節點進棧、出棧各一次
空間 $O (h)$ — 棧裡最多放一條從根往左的路徑

其中 $n$ 是節點數、h 是樹高（平衡樹 $O (\log n)$ 、斜樹 $O (n)$ ），都不含輸出的 res。

斜樹為什麼會退化：res = 左 + [自己] + 右 每一層都在建一個新的 list，把子樹的結果整份複製過去。左斜鏈的第 i 層要複製 i 個元素，加總起來就是 $1 + 2 + \dots + n = O (n^{2})$ 。