二叉树的层序遍历 II | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你二叉树的根节点 root，返回其节点值的 自底向上的层序遍历（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

节点数目在 [0, 2000] 内，节点值在 [-1000, 1000] 范围内。

示例 1

输入：root = [3,9,20,null,null,15,7]

输出：[[15,7],[9,20],[3]]

示例 2

输入：root = [1]

输出：[[1]]

示例 3

输入：root = []

输出：[]

💭 模拟答题者思考

1. 暴力直觉：和 #102 一样 BFS 得到 [[3],[9,20],[15,7]]，最后把整个外层列表反转——思路直接，代码也最短。

2. 重复在哪里？层内收集逻辑与 #102 完全相同，唯一差别是输出顺序：根层应在最后，叶子层应在最前。

3. 两种等价写法：① BFS 正常 append 每层，结束 ans.reverse()；② 每收集完一层就 ans.insert(0, level) 或双端队列 appendleft，省一次反转但单层插入头是 O(层数)，总仍 O(n²) 最坏——面试推荐先 BFS 再反转，整体 O(n) 且清晰。

4. 示例 1：BFS 得顶向下 [[3],[9,20],[15,7]]，反转后 [[15,7],[9,20],[3]]。

5. 每个节点仍只入队出队一次，时间 O(n)；空间 O(n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`q`	deque<TreeNode*>	定义：BFS 队列，与 #102 相同，按层从左到右扩展维护：每轮处理固定 `size` 个节点，保证一层一层推进更新：弹出节点后将其非空孩子按左→右入队
`level`	list<int>	定义：当前层从左到右的节点值维护：本轮内每弹出一个节点追加 `val` 更新：一层收集完后写入结果（见 `ans`）
`ans`	list<list<int>>	定义：自底向上的层序结果，`ans[0]` 为最底层维护：可先按顶向下 BFS 收集再整体 `reverse`，或每层 `insert(0, level)` / `appendleft` 更新：每完成一层即按题意顺序并入；空树返回 `[]`

⌨️ 落码步骤

1. 若 root 为空，返回 []

2. 用与 #102 相同的 BFS：队列、每层 size = len(q)、收集 level 并 ans.append(level)

3. BFS 结束后执行 ans.reverse()（或循环里每层 ans.insert(0, level)）

4. 返回 ans

💻 代码实现

from collections import deque

class Solution:
    def levelOrderBottom(self, root: TreeNode | None) -> list[list[int]]:
        if not root:
            return []
        ans: list[list[int]] = []
        q: deque[TreeNode] = deque([root])
        while q:
            level: list[int] = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(level)
        ans.reverse()
        return ans

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = (int)q.size();
            vector<int> level;
            for (int i = 0; i < size; ++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(std::move(level));
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)（队列最坏存满一层，约 n/2 个节点）

⚠️ 常见坑

❗ 忘记反转：直接返回 #102 的结果，根层在前，与题意相反。

❗ 在 BFS 内每层 reverse(level)：题意只要求「层与层」自底向上，层内仍从左到右，不要颠倒同层顺序。

❗ 与 #102 相同：不用固定 size 会导致层界混乱；空树须返回 []。

🔍 必测边界 Case

Case 1：空树

root = [] → []

Case 2：单节点

root = [1] → [[1]]

Case 3：官方示例 1

root = [3,9,20,null,null,15,7] → [[15,7],[9,20],[3]]

Case 4：只有左孩子（链）

root = [1,2,null,3] → [[3],[2],[1]]