剑指 Offer 32 - II 从上到下打印二叉树 II:按层分组的 BFS 层序遍历(doocs/leetcode 多语言解法全解)
剑指 Offer 32 - II 从上到下打印二叉树 II:按层分组的 BFS 层序遍历(doocs/leetcode 多语言解法全解)
本文以 doocs/leetcode 仓库中 面试题 32 - II. 从上到下打印二叉树 II 为核心,深入讲解"每一层单独成行"的二叉树层序遍历问题:为什么 BFS 天然匹配层序、如何通过"出队前记录队列长度"保住层与层之间的分界,以及仓库中 Python、Java、C++、Go、TypeScript、Rust、JavaScript、C# 八种语言的实现细节。读完本文,你将掌握"按层分组 BFS"这一通用模板,并能直接迁移到主站 102 题、剑指 Offer 32-I/32-III 等同类问题。
题目背景与题意解析
本题出自《剑指 Offer(第 2 版)》第 32 题第二问,仓库中对应的题目文档位于 lcof/面试题32 - II. 从上到下打印二叉树 II/README.md,难度标记为"简单"。
题目要求:从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。注意关键字——"每一层打印到一行",这与普通的扁平层序遍历(输出一维数组)不同,本题要求输出 List<List<Integer>> 这样的二维结构,每一层是一个独立数组。
示例推演
给定二叉树(层序表示为 [3,9,20,null,null,15,7]):
3
/ \
9 20
/ \
15 7
预期返回结果为:
[
[3],
[9,20],
[15,7]
]
其中第一层只有根节点 3;第二层按从左到右为 9、20;第三层为 15、7。可以观察到,示例树并不是完全二叉树——9 没有孩子节点(对应两个 null),但这不影响算法正确性,因为 BFS 只把实际存在的孩子节点入队。
约束与关联题
- 提示:
节点总数 <= 1000。这个规模意味着任何线性复杂度的解法(时间、空间均为 O(n))都绰绰有余,递归深度不会造成栈溢出风险。 - 注意:本题与 LeetCode 主站 102 题"二叉树的层序遍历"完全相同,题目文档中明确标注了这一等价关系。也就是说,掌握了本题解法,等于同时拿下主站 102 题。
核心思路:为什么是 BFS,以及如何保住"层界"
BFS 与层序的天然契合
"从上到下、同层从左到右"的访问顺序,本质上是广度优先遍历(BFS):先访问离根最近的节点,再逐层向外扩散。深度优先(DFS)会沿着一条分支走到底,打乱层序,因此不适用。BFS 借助队列"先进先出"的特性——先入队的节点先出队,父节点必然先于孩子节点被访问,且同一层的节点在队列中必然连续出现。
从源码结构看,仓库中本题全部八种语言实现 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs 全部采用 BFS + 队列的实现,无一例外。
关键技巧:出队前记录当前队列长度
普通 BFS 只需在出队时取值并把孩子入队即可,但那样会把所有层揉成一维数组(对应 32-I 的解法,见下文对比)。本题要求按层分组,难点在于:孩子节点会不断追加到队列尾部,如果边出队边入队,层与层的分界就会丢失。
原文档的"思考"块点破了破局点:
出队前记下当前队列长度,该批结点构成一层,收集后再入队下一层孩子。
也就是说,在每一轮循环开始时,队列中恰好装着当前层的全部节点(上一层处理结束时入队的)。此时用 len(q)(或 q.size()、queue.length)快照当前层节点数,然后只弹出这么多节点:
- 每弹出一个节点,把它的值写入临时数组
t; - 同时把它非空的孩子节点追加到队列尾部(这些孩子属于下一层,本轮不会碰它们)。
这样,一轮循环结束后,t 中恰好是当前层的全部值,而队列中剩下的恰好是下一层的全部节点,层与层被干净地切开。
算法流程(伪代码)
- 初始化结果数组
ans,若根节点为空直接返回ans(空树返回空列表); - 根节点入队
q; - 当队列不为空时,循环执行:
- 用
n = len(q)记录当前层节点数,初始化临时数组t; - 循环
n次:弹出队首节点,t追加其值;若左孩子非空则入队,若右孩子非空则入队; - 将
t追加到ans;
- 用
- 返回
ans。
复杂度分析
原文档给出的复杂度为:时间复杂度 O(n)、空间复杂度 O(n),其中 n 是二叉树的节点个数。
- 时间复杂度:每个节点恰好入队一次、出队一次,入队出队均为 O(1),因此总时间为 O(n)。
- 空间复杂度:队列中最多同时容纳某一层的全部节点,最坏情况(如完全二叉树的最后一层)节点数约为 n/2,故为 O(n);结果数组
ans本身也占用 O(n) 空间。
多语言实现与逐段解读
以下代码全部取自仓库中该题对应的 Solution 源文件,与 README 中的实现一致,可直接复制运行。
Python3
仓库文件:Solution.py
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t)
return ans
要点解读:
q = deque([root])使用collections.deque作为队列,popleft()是 O(1) 的头部弹出操作;若用普通 list 的pop(0)则是 O(n),会拖慢整体复杂度;for _ in range(len(q))的关键在于len(q)是在循环开始前求值的——Python 的range参数只计算一次,因此循环次数锁定为入队时的队列长度,后续q.append追加的下一层节点不会影响本次循环次数;- 空树时返回
ans(即空列表),这是一个必须处理的边界情况。
Java
仓库文件:Solution.java
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
List<Integer> t = new ArrayList<>();
for (int n = q.size(); n > 0; --n) {
TreeNode node = q.poll();
t.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
ans.add(t);
}
return ans;
}
}
要点解读:
- 选用
Deque<TreeNode> q = new ArrayDeque<>()作为队列:offer()队尾入队、poll()队首出队,均为 O(1); for (int n = q.size(); n > 0; --n)在循环初始化时用q.size()快照当前层节点数,循环体内每处理一个节点后n递减,恰好执行快照值次;循环中入队的下一层节点不会影响n;ArrayDeque不允许存放null元素,因此入队前必须用node.left != null做判空,这也是本题所有 Java 实现共同的细节。
C++
仓库文件:Solution.cpp
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> t;
for (int n = q.size(); n; --n) {
auto node = q.front();
q.pop();
t.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ans.push_back(t);
}
return ans;
}
};
要点解读:
queue<TreeNode*> q{{root}}用初始化列表直接把根节点放入队列,写法简洁;for (int n = q.size(); n; --n)用q.size()快照层节点数,n递减到 0 时循环结束;- 注意
auto node = q.front(); q.pop();的顺序:front()取队首指针,pop()弹出,二者不可颠倒(先 pop 再 front 是未定义行为)。
Go
仓库文件:Solution.go
func levelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return
}
q := []*TreeNode{root}
for len(q) > 0 {
t := []int{}
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
t = append(t, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
ans = append(ans, t)
}
return
}
要点解读:
- Go 直接用切片
q := []*TreeNode{root}模拟队列,q = q[1:]模拟队首出队; - 函数签名使用命名返回值
(ans [][]int),因此空树时直接return即可返回 nil 切片,语义上是"空结果"; q = q[1:]会共享底层数组、让底层数组前缀变成垃圾数据,对本题规模(节点数 <= 1000)完全够用;若追求极致内存复用,可改用带 head 指针的环形队列写法。
TypeScript
仓库文件:Solution.ts
function levelOrder(root: TreeNode | null): number[][] {
const res = [];
if (root == null) {
return res;
}
const queue = [root];
while (queue.length !== 0) {
const n = queue.length;
const tmp = new Array(n);
for (let i = 0; i < n; i++) {
const { val, left, right } = queue.shift();
tmp[i] = val;
left && queue.push(left);
right && queue.push(right);
}
res.push(tmp);
}
return res;
}
要点解读:
const n = queue.length在循环外快照当前层节点数,tmp = new Array(n)按层大小预分配数组,避免动态扩容;- 解构赋值
const { val, left, right } = queue.shift()一次性取出节点三要素,配合left && queue.push(left)的短路写法,代码非常紧凑; - 注意:
queue.shift()在 JavaScript 中是 O(n) 操作(数组头部移除需移动元素),但节点数 <= 1000 时影响可忽略;大规模场景可改用双端队列结构优化。
Rust
仓库文件:Solution.rs
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut res = Vec::new();
if root.is_none() {
return res;
}
let mut queue = VecDeque::new();
queue.push_back(root);
while !queue.is_empty() {
let n = queue.len();
let mut vals = Vec::with_capacity(n);
for _ in 0..n {
let mut node = queue.pop_front().unwrap();
let mut node = node.as_mut().unwrap().borrow_mut();
vals.push(node.val);
if node.left.is_some() {
queue.push_back(node.left.take());
}
if node.right.is_some() {
queue.push_back(node.right.take());
}
}
res.push(vals);
}
res
}
}
要点解读:
- 本题在 Rust 中最大的特点是所有权与借用管理:
TreeNode被包裹在Option<Rc<RefCell<TreeNode>>>中,需要borrow_mut()获取可变借用才能读写val、left、right; node.left.take()会把左孩子从Option中取出(留下None),正好满足"把左孩子所有权转移给队列"的需求,是 Rust 处理树结构时的惯用写法;VecDeque::new()是标准库的双端队列,pop_front()为 O(1);Vec::with_capacity(n)按层大小预分配容量。
JavaScript
仓库文件:Solution.js
var levelOrder = function (root) {
let ans = [];
if (!root) {
return ans;
}
let q = [root];
while (q.length) {
let t = [];
for (let n = q.length; n; --n) {
const { val, left, right } = q.shift();
t.push(val);
left && q.push(left);
right && q.push(right);
}
ans.push(t);
}
return ans;
};
要点解读:
- 与 TypeScript 版本思路一致,
for (let n = q.length; n; --n)用递减计数锁定当前层节点数; if (!root)同时覆盖null与undefined两种空值情况。
C#
仓库文件:Solution.cs
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root) {
if (root == null) {
return new List<IList<int>>();
}
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(root);
List<IList<int>> ans = new List<IList<int>>();
while (q.Count != 0) {
List<int> tmp = new List<int>();
int x = q.Count;
for (int i = 0; i < x; i++) {
TreeNode node = q.Dequeue();
tmp.Add(node.val);
if (node.left != null) {
q.Enqueue(node.left);
}
if (node.right != null) {
q.Enqueue(node.right);
}
}
ans.Add(tmp);
}
return ans;
}
}
要点解读:
- 使用 BCL 自带的
Queue<TreeNode>,Enqueue/Dequeue均为 O(1); int x = q.Count;在循环外快照当前层节点数,与其余语言的len(q)快照技巧完全同构;- 返回类型为
IList<IList<int>>(泛型接口),实现时使用List<IList<int>>,符合 .NET 的接口编程惯例。
边界情况与易错点
空树处理
所有语言的实现都在最开始判空:空树时直接返回空结果(ans/res),而不是报错或进入循环。这一点在原文档的 Python 实现(if root is None: return ans)和其余语言实现中均有体现。凡是涉及树结构的 BFS/DFS 题,判空永远是第一步。
快照顺序不能错
核心易错点是"先快照、后遍历":n = len(q) 必须在处理本层节点之前完成。如果边出队边取 len(q),由于孩子入队会改变队列长度,层界立刻丢失,结果退化成 32-I 的扁平输出。八种语言实现全部严格遵守"循环外快照"这一约定。
孩子判空
入队孩子节点前必须判空(如 Java 的 node.left != null、Go 的 node.Left != nil)。如果盲目把 null 入队,后续解引用会抛出空指针异常;在 Rust 中 queue.push_back(node.left.take()) 只在 is_some() 时执行,语义上等价。
与同系列题目对比:32-I、32-III 的递进关系
本题位于"从上到下打印二叉树"三连问的中间位置,仓库中三题文档齐全,可以对照学习:
| 题目 | 输出结构 | 核心差异 |
|---|---|---|
| 面试题 32 - I. 从上到下打印二叉树 | 一维数组 [3,9,20,15,7] |
只需 BFS 扁平收集,无需按层分组,对应"基础版" |
| 面试题 32 - II. 从上到下打印二叉树 II(本题) | 二维数组 [[3],[9,20],[15,7]] |
出队前记录队列长度,按层分组,对应"进阶版" |
| 面试题 32 - III. 从上到下打印二叉树 III | 之字形 [[3],[20,9],[15,7]] |
在 II 的基础上,偶数层(从 0 计数)结果反转,对应"变式版" |
三题的骨架完全一致——BFS + 队列 + 层长度快照;区别仅在于输出结构(扁平/分组/反转)。仓库中 面试题 32 - III 的解法文档 明确给出了其变式策略:每收集完一层,若当前结果数组长度为奇数则反转该层再写入。也就是说,吃透本题的"按层分组 BFS"模板,同一家族的 32-I、32-III 与主站 102 题均可一通百通。
小结
本题是"按层分组 BFS"的教科书级题目,其技术要点可归纳为三条:
- BFS 是层序遍历的正确范式:队列的先进先出特性天然保证"先上后下、同层从左到右";
- 层长度快照是分组的关键:每轮循环开始时用
len(q)/q.size()/q.length锁定本层节点数,把本层的出队与下一层的入队隔离在两个阶段; - 复杂度恒定为线性:每个节点入队出队各一次,时间 O(n)、空间 O(n),与树形无关,只与节点总数相关。
仓库中该题的完整题目文档位于 lcof/面试题32 - II. 从上到下打印二叉树 II/README.md,八种语言的独立实现分别存放在同目录下的 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs 中,可以直接作为各语言的标准模板参考。建议读者对照这些源码,亲手运行并验证空树、单节点、满二叉树、非完全二叉树等各类输入,彻底掌握这一高频面试考点。