LeetCode 107 二叉樹層序遍歷 II：自底向上輸出節點值

題目描述

給定一棵二叉樹，返回其節點值的自底向上層序遍歷結果（即從葉子層到根層，每層從左到右）。

範例：

輸入: {3,9,20,#,#,15,7}
    3
   / \
  9  20
    /  \
   15   7

輸出: [[15,7], [9,20], [3]]

解題思路：BFS + 反轉結果

層序遍歷（BFS）天然從上到下，我們只需正常 BFS 收集每層節點值，最後將結果列表反轉即可。

1. 使用佇列存儲 (節點, 層級) 對
2. 用 map<int, vector<int>> 或 vector<vector<int>> 按層級收集節點值
3. 遍歷結束後，從最大層級遞減輸出，或直接 reverse 結果列表

時間複雜度：O(n)，空間複雜度：O(n)。

C++ 參考實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        vector> ans;
        if (!root) return ans;
        
        queue> q;
        map> levelMap;
        
        q.push({root, 0});
        
        while (!q.empty()) {
            auto [node, level] = q.front();
            q.pop();
            
            levelMap[level].push_back(node->val);
            
            if (node->left) q.push({node->left, level + 1});
            if (node->right) q.push({node->right, level + 1});
        }
        
        // 從最大層級遞減輸出
        for (auto it = levelMap.rbegin(); it != levelMap.rend(); ++it) {
            ans.push_back(it->second);
        }
        return ans;
    }
};

優化版：直接用 vector 收集再反轉

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        vector> ans;
        if (!root) return ans;
        
        queue q;
        q.push(root);
        
        while (!q.empty()) {
            int sz = q.size();
            vector level;
            for (int i = 0; i < sz; ++i) {
                TreeNode* node = q.front(); q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans.push_back(level);
        }
        
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

核心要點總結

• BFS 模板：佇列 + 當前層節點數 sz 控制逐層遍歷
• 反轉技巧：reverse 或反向迭代器 rbegin/rend 實現自底向上
• 對比題目：LeetCode 102 為自頂向下，僅輸出順序不同

掌握「BFS 分層 + 結果反轉」模式，可輕鬆解決所有層序遍歷變體問題。