Trees · LeetNote

樹是階層式的資料結構，由節點和邊組成。二元樹、二元搜尋樹 (BST) 是最常見的變體。遞迴是處理樹問題的核心技巧。

Notes:

大多數樹的題目可以用 DFS（前序/中序/後序）或 BFS（層序遍歷）解決
BST 的中序遍歷會產生有序序列，這個性質非常有用
遞迴解法要注意 base case 和回傳值的設計

為什麼樹天生適合遞迴

樹的定義本身就是遞迴的：「一棵樹 = 一個根節點 + 若干棵子樹，而每棵子樹也是一棵樹」。所以處理樹時，只要想清楚「對當前節點做什麼」「把同樣的事交給左右子樹」，三五行就能寫完。這也是一種自頂向下的思維——不像人類習慣的由小累積（遞推），而是先假設子問題已解決，再合併。接受這個思維，樹的遍歷會變得異常簡潔。

DFS：三種遍歷

差別只在「處理根節點」這一步放在遞迴的哪個位置：

遍歷	順序	常見用途
前序 (preorder)	根 → 左 → 右	複製樹、序列化
中序 (inorder)	左 → 根 → 右	BST 取得有序序列
後序 (postorder)	左 → 右 → 根	先處理子樹再處理根（刪除、算高度/直徑）

fun inorder(node: TreeNode?, out: MutableList<Int>) {
    if (node == null) return        // base case
    inorder(node.left, out)
    out.add(node.`val`)             // 中序：在左右之間處理根
    inorder(node.right, out)
}

BFS：層序遍歷

用佇列逐層展開，適合「最短路徑（無權）」「逐層處理」「找某層的值」。

fun levelOrder(root: TreeNode?): List<List<Int>> {
    val res = mutableListOf<List<Int>>()
    if (root == null) return res
    val queue = ArrayDeque<TreeNode>()
    queue.add(root)
    while (queue.isNotEmpty()) {
        val level = mutableListOf<Int>()
        repeat(queue.size) {              // 固定當層節點數
            val node = queue.removeFirst()
            level.add(node.`val`)
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        res.add(level)
    }
    return res
}

DFS vs BFS 複雜度

	時間	空間
DFS	`O(n)`	`O(h)`，h 為樹高（遞迴堆疊）
BFS	`O(n)`	`O(n)`，最寬一層的節點數

TIP

樹接近平衡時 h ≈ log n，DFS 空間較省；但若樹退化成鏈狀（h = n），DFS 的遞迴堆疊也會到 O(n)，甚至堆疊溢位。要找「最淺」的目標時，BFS 通常更直接。

跨倉庫導讀

對應理論章節：樹