CS-Notes 剑指 Offer 32.2：把二叉树打印成多行——基于 BFS 队列的按层分组遍历详解

本文基于 CS-Notes 仓库中的 32.2 把二叉树打印成多行 一题展开，系统讲解如何用一个队列配合"当前层节点计数"技巧，将二叉树按层输出为二维列表（List<List<Integer>>）。读完后你将掌握层次遍历（BFS）中"按层切分结果"的核心手法，并理解它与第 32.1 题（单层扁平输出）、第 32.3 题（之字形输出）之间的递进关系，能够举一反三地解决 Leetcode 层次遍历类题目。

题目描述

第 32.2 题的题目描述与上一题几乎一致，只是输出格式从"一维列表"升级为"二维列表"：

从上到下打印出二叉树的每个节点，同一层的节点打到一行，每一层打印一行。

例如对如下二叉树：

        1
      /   \
     2     3
    / \     \
   4   5     6

期望输出为：

[1]
[2, 3]
[4, 5, 6]

该题与 32.1 从上往下打印二叉树、32.3 按之字形顺序打印二叉树 同属"树的打印"问题组，在 剑指 Offer 题解 - 目录 中三者并列收录，核心数据结构均为队列，难度逐题递进。

核心思路：BFS 固定长度遍历实现"按层分组"

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性。32.2 题的关键在于：不需要使用两个队列分别存储当前层的节点和下一层的节点——在开始遍历某一层时，当前队列中的节点数就是该层的节点数，只要"固定"这一轮只弹出这么多节点，就能保证本轮处理的全部是当前层的节点。

仓库中 32.1 从上往下打印二叉树 对这一技巧有更完整的阐述，32.2 在其基础上只需增加一个"每层独立列表"的分组动作。完整解法代码如下（与 32.2 把二叉树打印成多行 原文档一致）：

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    while (!queue.isEmpty()) {
        ArrayList<Integer> list = new ArrayList<>();
        int cnt = queue.size();
        while (cnt-- > 0) {
            TreeNode node = queue.poll();
            if (node == null)
                continue;
            list.add(node.val);
            queue.add(node.left);
            queue.add(node.right);
        }
        if (list.size() != 0)
            ret.add(list);
    }
    return ret;
}

逐段解析关键实现细节

1. int cnt = queue.size() 是"层边界"的唯一来源

外层 while 每执行一轮，就处理"一层"。在进入内层循环前用 cnt = queue.size() 快照当前队列长度，内层循环恰好弹出 cnt 个节点。弹出这 cnt 个节点的过程中新入队的节点属于下一层，不会影响本轮计数，从而天然实现了层的划分。这与 Leetcode 题解 - 树 "层次遍历"一节中 637 题（一棵树每层节点的平均数）的写法完全同构：

while (!queue.isEmpty()) {
    int cnt = queue.size();
    double sum = 0;
    for (int i = 0; i < cnt; i++) {
        TreeNode node = queue.poll();
        sum += node.val;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    ret.add(sum / cnt);
}

两处代码的差异仅在于每层的聚合方式：637 题聚合为 sum / cnt，32.2 题聚合为一个 ArrayList。

2. 为什么可以"入队 null"

注意原文档的实现是 queue.add(node.left) / queue.add(node.right)，不做判空，允许 null 子节点入队；对应地，弹出时需要 if (node == null) continue; 跳过。这是该解法的一个风格选择：

• 入队时不判空，代码更简洁，但队列中会混入 null，弹出时必然要判空；
• 另一种等价写法是入队时判空（if (node.left != null) queue.add(node.left);），队列中始终只有真实节点，弹出时也无需判空。

两种写法时间复杂度相同，面试中任选其一并说明即可。注意 queue.size() 统计的是"当前层"的长度，null 也被计入其中，但内层循环固定按 cnt 次弹出，因此不会因为 null 的进出而破坏层边界。

3. 空树与空层的过滤

• 根节点为 null 时，初始 queue.add(null) 后第一轮内层循环弹出 null 被跳过，list 为空，if (list.size() != 0) 保证不会把空列表加入结果，最终返回空列表；
• 对于中间层不存在"某层为空但更下层非空"的情况（二叉树的层是连续的），因此 list.size() != 0 这一判断实际主要服务于空根输入，保证输出结果的规整性。

4. 队列的底层实现

Queue<TreeNode> queue = new LinkedList<>() 使用 LinkedList 实现队列。从仓库 Java 容器 中的说明可以确认：LinkedList 基于双向链表实现，可以快速在链表头尾插入删除元素，因此既可以做栈、也可以做队列，其 add（入队）与 poll（出队）均为 O(1) 操作，这正是 BFS 选它作为容器实现的原因。

与 32.1 / 32.3 的对比：同一模板的三次演进

32 题组三题共享"单队列 + 固定长度遍历"骨架，差异只在每层结果的整理方式：

题目	每层处理差异	结果类型
32.1 从上往下打印二叉树	所有节点追加到同一个 ret	ArrayList<Integer>
32.2 把二叉树打印成多行	每层单独建一个 list，非空时加入 ret	ArrayList<ArrayList<Integer>>
32.3 按之字形顺序打印二叉树	在 32.2 基础上用 reverse 标志位，奇数层 Collections.reverse(list)	ArrayList<ArrayList<Integer>>

以 32.3 为例，其代码在 32.2 骨架上仅多了三行（引自 32.3 按之字形顺序打印二叉树）：

boolean reverse = false;
// 内层循环结束后：
if (reverse)
    Collections.reverse(list);
reverse = !reverse;

反过来也可以说，32.2 是 32.1 与 32.3 之间的"过渡形态"：掌握了 32.2 的按层分组，就同时具备了另外两题的全部基础设施。

复杂度分析

设二叉树共有 n 个节点：

• 时间复杂度 O(n)：每个节点恰好入队一次、出队一次，每层一次的 ArrayList 创建与 ret.add 均为 O(1) 摊还成本；若采用 32.3 的 Collections.reverse，额外 O(层宽) 的翻转成本总计仍是 O(n)。
• 空间复杂度 O(n)：队列在最坏情况下（如完全二叉树的最后一层）保存 O(n) 个节点，输出结果本身也保存全部 n 个节点值。

小结与延伸

32.2 的价值在于提供了一个"按层分组"的标准模板：while (!queue.isEmpty()) 控制层数，cnt = queue.size() 控制每层弹出的节点数，层内结果统一聚合。掌握它之后，可直接迁移到 Leetcode 题解 - 树 层次遍历章节的其他题目，例如 637 每层节点的平均数（聚合为均值）、513 左下角节点（每层最左元素即该层第一个出队节点）。此外，仓库中的 算法 - 栈和队列 给出了基于链表的手写队列实现（维护 first/last 指针），可用于理解 Queue 接口背后的底层机制，进一步加深对 add/poll 操作 O(1) 特性的认识。