二叉树的层序遍历 II 图解题解

这道题到底在问什么

输入

[3,9,20,null,null,15,7]

输出

[[15,7],[9,20],[3]]

输入

单节点 [1]

输出

[[1]]

最优解：一步一步想明白

1. 3记住「正常 BFS 按层收 → 最后整层倒序」,下面逐帧套它。注意每层是整层一起收下,再去找下一层。
2. 4按深度分层先找感觉:同一深度的节点属于同一层。根 3 是第 0 层,它的孩子 9、20 是第 1 层,再往下 15、7 是第 2 层。BFS 正是一层接一层地访问。
3. 5本层 1 个节点进入第 0 层,队列里是 [3]。这一层先整层收下,再去找它们的孩子组成下一层。
4. 6收下 3从队首取出 3(标红),把它的值收进第 0 层的列表,现在本层是 [3]。
5. 73 → 9,203 处理完(变绿)。把它的非空孩子 9、20(蓝色)加入下一层,目前下一层攒到了 [9、20]。
6. 8第 0 层 = [3]第 0 层整层收齐 = [3]。下一层 [9、20] 已就绪,继续往下。
7. 9本层 2 个节点进入第 1 层,队列里是 [9、20]。这一层先整层收下,再去找它们的孩子组成下一层。
8. 10收下 9从队首取出 9(标红),把它的值收进第 1 层的列表,现在本层是 [9]。
9. 119 是叶子9 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。
10. 12收下 20从队首取出 20(标红),把它的值收进第 1 层的列表,现在本层是 [9、20]。
11. 1320 → 15,720 处理完(变绿)。把它的非空孩子 15、7(蓝色)加入下一层,目前下一层攒到了 [15、7]。
12. 14第 1 层 = [9,20]第 1 层整层收齐 = [9、20]。下一层 [15、7] 已就绪,继续往下。
13. 15本层 2 个节点进入第 2 层,队列里是 [15、7]。这一层先整层收下,再去找它们的孩子组成下一层。
14. 16收下 15从队首取出 15(标红),把它的值收进第 2 层的列表,现在本层是 [15]。
15. 1715 是叶子15 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。
16. 18收下 7从队首取出 7(标红),把它的值收进第 2 层的列表,现在本层是 [15、7]。
17. 197 是叶子7 是叶子,没有孩子可加(变绿),下一层暂时还是 [空]。
18. 20第 2 层 = [15,7]第 2 层整层收齐 = [15、7]。没有下一层了,BFS 即将结束。
19. 21自顶向下 3 层队列空了,BFS 结束。自顶向下收集到 [[3], [9,20], [15,7]]。但题目要的是自底向上,所以最后把这些层整体倒过来。
20. 22放入 [15,7]倒序第 1 步:把原来的第 2 层 [15、7](高亮)放到结果里。现在自底向上结果是 [[15,7]]。
21. 23放入 [9,20]倒序第 2 步:把原来的第 1 层 [9、20](高亮)放到结果里。现在自底向上结果是 [[15,7], [9,20]]。
22. 24放入 [3]倒序第 3 步:把原来的第 0 层 [3](高亮)放到结果里。现在自底向上结果是 [[15,7], [9,20], [3]]。
23. 25答案 = [[15,7], [9,20], [3]]自底向上的层序遍历就是 [[15,7], [9,20], [3]]:最底层 [15、7] 排最前,根 [3] 在最后。回头看,就是一遍正常 BFS 按层收集,末尾整体倒序,时间 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        q, ans = [root], []
        while q:
            ans.append([n.val for n in q])
            q = [c for n in q for c in (n.left, n.right) if c]
        return ans[::-1]

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (!root) return {};
        queue<TreeNode*> q; q.push(root);
        vector<vector<int>> ans;
        while (!q.empty()) {
            vector<int> row;
            for (int sz = q.size(); sz--; ) {
                auto n = q.front(); q.pop(); row.push_back(n->val);
                if (n->left) q.push(n->left);
                if (n->right) q.push(n->right);
            }
            ans.push_back(row);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> ans = new LinkedList<>();
        if (root == null) return ans;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            for (int sz = q.size(); sz > 0; sz--) {
                TreeNode n = q.poll(); row.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            ans.addFirst(row);
        }
        return ans;
    }
}

复杂度

面试官可能追问