← All notes
LeetCode Cycle 09：樹的基礎、BST 與三種 traversal
樹這題在面試常見的失誤不是寫不出 traversal，是搞不清「為什麼挑 inorder 不挑 preorder」「BFS 為什麼配 queue 不配 stack」。Cycle 09 把 [Cycle 06 stack] + [Cycle 07 遞迴] + [Cycle 01 binary search] 三條線收攏成一個結構。內部使用。
Cycle 09 排在 backtracking 之後其實是順理成章——Cycle 08 把遞迴詮釋成「樹形搜索」，Cycle 09 進來把那棵樹真的拿出來操作。前面三條線在這裡會合：
- Cycle 01 binary search 的 O(log n)：在 BST 上重現
- Cycle 06 stack：iterative traversal 用到
- Cycle 07 recursion：三部曲還是同一套
面試 tree 題的判定點不是「能不能寫出來」，而是「為什麼挑這個 traversal」。看到 BST 沒人挑 preorder，看到「先處理子節點再處理自己」沒人挑 BFS——這條對應關係要熟到自動反射。
四種樹
| 類型 | 定義 |
|---|---|
| 滿二元樹（full） | 每個節點要嘛 0 子要嘛 2 子，所有葉子在同一層 |
| 完全二元樹（complete） | 除了最後一層，每層都滿；最後一層節點靠左排 |
| 二元搜尋樹（BST） | 左子樹所有節點 < 自己 < 右子樹所有節點，遞迴成立[^1]；每次找值可砍掉一半子樹，平衡時 O(log n) |
| 平衡 BST | 在 BST 基礎上加：每個節點左右子樹高度差 ≤ 1 |