LeetCode 107. 二叉樹層序遍歷 II：自底向上 BFS 遞歸實現

題目描述

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

示例：輸入 {3,9,20,#,#,15,7}，輸出 [[15,7],[9,20],[3]]。

核心思路：遞歸 DFS + 層級記錄 + 最後反轉

利用遞歸前序遍歷，攜帶當前層級 level 參數。將節點值加入 result[level-1]。遍歷結束後 reverse(result) 即得自底向上順序。

C++ 完整實現

// 使用隊列層序遍歷，最後反轉結果
vector> levelOrderBottom(TreeNode* root) {
    vector> res;
    if (!root) return res;
    queue q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector level;
        while (sz--) {
            auto node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(move(level));
    }
    reverse(res.begin(), res.end());
    return res;
}

BFS 避免遞歸棧溢出風險，更適合深度極大的樹。

總結

本題是「二叉樹層序遍歷」的簡單變體，核心在於最後反轉結果向量。掌握 DFS 與 BFS 兩種遍歷模板，靈活應對變體題。