剑指 Offer 32 - II 从上到下打印二叉树 II:按层分组的 BFS 层序遍历(doocs/leetcode 多语言解法全解)

原创2026-10-14 13:25:552,203 阅读
文章标签:教程示例工程教育

剑指 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 中恰好是当前层的全部值,而队列中剩下的恰好是下一层的全部节点,层与层被干净地切开。

算法流程(伪代码)

  1. 初始化结果数组 ans,若根节点为空直接返回 ans(空树返回空列表);
  2. 根节点入队 q;
  3. 当队列不为空时,循环执行:
    • 用 n = len(q) 记录当前层节点数,初始化临时数组 t;
    • 循环 n 次:弹出队首节点,t 追加其值;若左孩子非空则入队,若右孩子非空则入队;
    • 将 t 追加到 ans;
  4. 返回 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"的教科书级题目,其技术要点可归纳为三条:

  1. BFS 是层序遍历的正确范式:队列的先进先出特性天然保证"先上后下、同层从左到右";
  2. 层长度快照是分组的关键:每轮循环开始时用 len(q)/q.size()/q.length 锁定本层节点数,把本层的出队与下一层的入队隔离在两个阶段;
  3. 复杂度恒定为线性:每个节点入队出队各一次,时间 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 中,可以直接作为各语言的标准模板参考。建议读者对照这些源码,亲手运行并验证空树、单节点、满二叉树、非完全二叉树等各类输入,彻底掌握这一高频面试考点。

登录后查看全文
leetcode