MediumRating 1436
107. Binary Tree Level Order Traversal II
treebreadth-first-searchbinary-tree
解題說明
Binary Tree Level Order Traversal II
題目描述：給定一棵二元樹的根節點 root，以「由下至上、由左至右」的順序，逐層回傳節點值（即葉節點所在的層先回傳，根節點所在的層最後回傳）。
解題思路：本題是標準「層序遍歷（BFS）」的變形，差別僅在於最終結果需要反轉。
解法步驟：
- 使用一個佇列進行 BFS，每次處理整層的節點。
- 將每一層的節點值收集為一個
vector<int>，加入結果列表result。 - 全部層處理完畢後，呼叫
reverse(result.begin(), result.end())將結果反轉，即可得到由下至上的順序。
另一種等價做法是使用 deque 作為結果容器，每收集完一層便用 push_front 插入至最前端，省去最後的反轉步驟，但反轉解法更直觀易讀。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點恰好入佇列與出佇列各一次，最後的反轉操作為 O(層數) ≤ O(n)，整體為 O(n)。
空間複雜度：O(n) — 佇列在最壞情況下（完全二元樹最底層）需儲存約 n/2 個節點；結果陣列儲存所有 n 個節點的值，故空間為 O(n)。
虛擬碼
1. If root is null, return empty list.
2. Initialize queue with root; initialize result list.
3. While queue is not empty:
a. Record current queue size as levelSize.
b. Create an empty level list.
c. For i from 0 to levelSize - 1:
- Dequeue node; append node.val to level list.
- Enqueue node.left if not null.
- Enqueue node.right if not null.
d. Append level list to result.
4. Reverse result list.
5. Return result.其他解法
方法一：BFS + deque 前插（避免反轉）
- 使用
deque<vector<int>>作為結果容器，每完成一層就以push_front將該層插入最前端，天然得到由下至上的順序，無需最後的reverse步驟。程式碼略簡潔，但push_front在deque上為 O(1)，實際效能與反轉法相當。 - 時間複雜度：O(n)，空間複雜度：O(n)
方法二：遞迴 DFS
- 以 DFS 遍歷樹，同時紀錄當前深度。先完成整棵樹的遍歷再決定插入哪一層。由於最大深度未知，訪問每個節點時需先確認結果陣列大小是否足夠並在必要時在前端插入新的空 vector。相較 BFS 不直觀，但可作為練習遞迴的替代解。
- 時間複雜度：O(n)，空間複雜度：O(h)（遞迴堆疊深度為樹高 h）
延伸思考
- 若要求同時輸出「由上至下」和「由下至上」兩種層序遍歷結果，如何以一次 BFS 完成，避免重複遍歷？
- 如何修改本題解法以處理 N 叉樹（每個節點可有任意多個子節點）的由下至上層序遍歷？
- 在記憶體極度受限的場景中，若無法儲存整層節點，有哪些方式可以估算樹的層數並決定插入位置？