題目描述:給定一棵二元樹的根節點 root,以「由下至上、由左至右」的順序,逐層回傳節點值(即葉節點所在的層先回傳,根節點所在的層最後回傳)。
解題思路:本題是標準「層序遍歷(BFS)」的變形,差別僅在於最終結果需要反轉。
解法步驟:
vector<int>,加入結果列表 result。reverse(result.begin(), result.end()) 將結果反轉,即可得到由下至上的順序。另一種等價做法是使用 deque 作為結果容器,每收集完一層便用 push_front 插入至最前端,省去最後的反轉步驟,但反轉解法更直觀易讀。
時間複雜度: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),實際效能與反轉法相當。方法二:遞迴 DFS