企业官网建设流程全解析

CS-Notes 剑指 Offer 32.3 详解：按之字形顺序打印二叉树（BFS 逐层遍历 + 奇偶层翻转）

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes

本篇技术指南基于 CS-Notes 仓库中《剑指 Offer》题解系列的 32.3 按之字形顺序打印二叉树 展开，完整讲解之字形（锯齿形）层次遍历的题目要求、基于队列的 BFS 官方解法逐行剖析，以及 deque 免翻转的替代实现与复杂度分析。读完本篇，你能掌握"单队列 + 层内计数"这一层次遍历的通用骨架，理解为什么只需一个布尔标记即可控制打印方向，并能把同一套思路复用到 32.1、32.2 及各类变体题目上。

题目描述与核心目标

原题来自《剑指 Offer》第 32 题系列的第三问（题目原文见 notes/32.3 按之字形顺序打印二叉树.md）：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

以一棵样例二叉树为例：

8 / \ 6 10 / \ / \ 5 7 9 11

各层节点数值为[8]、[6, 10]、[5, 7, 9, 11]。之字形要求输出：

[[8], [10, 6], [5, 7, 9, 11]]

即偶数层（从第 1 层起算）保持左到右，奇数层整体反转。接口签名沿用牛客/剑指 Offer 的桩函数：

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ... }

返回值是"每层一个子列表"的二维结构。这一点很关键：它决定了算法必须"按层分组"，而不像 32.1 那样把所有节点拍平成一个列表。

前置基础：单队列逐层遍历的通用骨架

32.3 并不是凭空出现的技巧，它建立在同系列前两题之上：32.1 从上往下打印二叉树 与 32.2 把二叉树打印成多行。仓库中 32.1 的题解给出了层次遍历最核心的思想（见 32.1 题解）：

不需要使用两个队列分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

这个"层内计数"技巧是整组题目的骨架：

1. 每轮外层循环开始时，先记录queue.size()，这就是当前层的节点个数cnt；
2. 内层循环恰好弹出cnt个节点，弹出时把它们的子节点入队——子节点全部属于下一层，因此下一轮queue.size()恰好等于下一层节点数；
3. 无需额外数组、无需"当前层队列 + 下一层队列"的双队列结构。

32.1 的输出是所有节点拍平的一维列表；32.2 只是把每层的收集结果list独立存进结果二维数组；32.3 则在此基础上多了一步——对奇数层的list做反转。三题的递进关系可以概括为：

官方解法：队列 BFS + Collections.reverse

下面是 32.3 题解 给出的完整解法（仓库原文，可直接复制到牛客对应题目运行）：

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.add(pRoot); boolean reverse = false; 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 (reverse) Collections.reverse(list); reverse = !reverse; if (list.size() != 0) ret.add(list); } return ret; }

逐段拆解其设计要点：

1）入口即入队，不判空

queue.add(pRoot)之后直接进入主循环，没有if (pRoot == null)的前置判断。原因是该写法把null视为合法的"队内占位"：根为空时，队列里只有一个null，第一轮循环弹出后即被continue跳过，list为空，最后list.size() != 0不成立，ret保持空列表——空树直接返回[]，无需单独分支。

2）cnt在层开始时刻"快照"

int cnt = queue.size()是层遍历的锚点。注意此刻队列中混有上一轮入队的null（某节点缺失的左/右子节点也会以null入队），cnt统计的是"占位数"而非实际节点数，内层循环恰好消费完当前层全部占位，下一轮queue.size()自然就是下一层的占位数，逐层推进直到队列耗尽。

3）null 容错：if (node == null) continue

由于左右子节点不加判空地queue.add，队列中必然出现null。continue保证只对真实节点取val、入子节点，同时保持了"占位数与下一层规模"的对应关系不被破坏。这是一种用空间换分支简洁性的写法：每层末尾的两个null子节点会一直留到树的最底层才被消费完，属于少量常数级冗余，不影响正确性。

4）方向控制：一个布尔标记

boolean reverse = false; // 第一层不反转 ... if (reverse) Collections.reverse(list); reverse = !reverse; // 每处理完一层翻转方向

reverse初始为false，第一层（偶数层）正序入列；每处理完一层就取反，使第二层（奇数层）反转。Collections.reverse(list)是原地反转，均摊复杂度 O(层节点数)，整棵树所有层的反转总代价不超过 O(n)。注意翻转必须发生在该层list收集完之后、入结果之前，不能在内层循环里边取边反转。

5）空层过滤：if (list.size() != 0)

由于 null 占位会一直"陪跑"到最底层，队列耗尽前的若干轮可能只弹出null，得到空list。该条件保证空层不会进入结果数组，最终输出与"实际存在的层数"严格一致。

替代实现：deque 双向队列，免反转

上面的解法"先按左到右收集，再原地反转"，直观但每层要额外走一遍。也可以从访问顺序入手，让队列本身按打印方向出队——用Deque（LinkedList同时实现了Deque和Queue）：偶数层从队首出队、子节点追加到队尾；奇数层从队尾出队、子节点插到队头。这样每层的line天然就是打印顺序，省掉Collections.reverse：

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (pRoot == null) return ret; Deque<TreeNode> deque = new LinkedList<>(); deque.offer(pRoot); boolean leftToRight = true; while (!deque.isEmpty()) { int size = deque.size(); ArrayList<Integer> line = new ArrayList<>(); for (int i = 0; i < size; i++) { if (leftToRight) { // 偶数层：队首出，子节点进队尾，保持下一层队首是最左节点 TreeNode node = deque.pollFirst(); line.add(node.val); if (node.left != null) deque.offerLast(node.left); if (node.right != null) deque.offerLast(node.right); } else { // 奇数层：队尾出，子节点进队头 TreeNode node = deque.pollLast(); line.add(node.val); if (node.right != null) deque.offerFirst(node.right); if (node.left != null) deque.offerFirst(node.left); } } leftToRight = !leftToRight; ret.add(line); } return ret; }

两种实现的取舍：

• 官方解法：入队不判空、空树不用前置判空，代码分支更少；代价是奇数层多一次原地反转，且队列中残留 null 占位。
• deque 解法：入队时判空（offer前判null），队列中始终是真实节点，size即真实节点数；每层访问方向与打印方向一致，无反转开销；代价是奇数层分支里"右子先于左子入队"的方向细节更容易写错。

两者空间复杂度同为 O(n)（最坏斜树下队列持有 O(n) 节点），时间复杂度同为 O(n)（每个节点恰好入队、出队一次，官方解法的反转开销均摊进 O(n)）。面试中推荐先讲官方解法体现"层内计数"骨架，再补 deque 解法展示对双向队列的驾驭。

关键细节与易错点

结合仓库原题解的写法，梳理实现该题时最容易踩坑的四处：

1. 反转时机：必须在整层收集完后统一reverse，而不是出队时就决定方向；前者依赖"队列内层内节点天然从左到右"这一不变式。
2. 空树返回：接口要求返回"层的列表"，空树应返回空列表[]而非null。官方解法通过 null 占位 + 空层过滤天然达成；deque 解法则需要显式if (pRoot == null) return ret。
3. cnt与size的关系：官方解法中cnt包含 null 占位，是"占位规模"；deque 解法中size是"真实节点规模"。混用两套语义（例如 deque 解法里入队不判空）会破坏逐层推进的正确性。
4. 单节点/斜树退化：链状树每层只有一个真实节点，方向翻转对单元素层无可见效果，但reverse标记仍须逐层取反，不能因"这层只有一个节点"而提前终止或跳过翻转，否则后续层方向错乱。

复杂度小结

设树有 n 个节点、高度为 h：

迭代实现也顺带规避了树高度 O(h) 的递归栈溢出风险，在极不平衡的树上是相对递归 DFS 的一个实际优势。

变体延伸与仓库内学习路径

之字形打印的骨架（单队列 + 层内计数）还可以直接复用到相邻变体：

• 拍平输出：若题目要求输出单一列表1, 2, 3, 4, 5, 6, 7且奇数层反转，只需把每层list顺序追加到一个总列表即可，见 32.1 从上往下打印二叉树。
• 按行输出：每层一个子列表但不反转，见 32.2 把二叉树打印成多行。
• 之字形拍平（奇偶层方向交替的单列表）：在 32.3 的循环内，不收集二维结果，而是把list（反转后）逐元素追加进一维列表，即得之字形单行输出，常见于 LeetCode 116 系列的变体题。
• 逐层聚合统计：如"每层求和/求平均"，把list.add(node.val)换成累加器即可，同一套循环框架通用。

在 CS-Notes 仓库内，建议按如下顺序串起学习闭环：

1. 剑指 Offer 题解 - 目录 的"树"章节，定位 32.1 → 32.2 → 32.3 三连题，体会同一 BFS 骨架的三次演进；
2. Leetcode 题解 - 树 中的"层次遍历"小节，补充"每层节点平均数""得到左下角节点"等基于同一队列模式的题目，巩固层内计数的熟练度。

总结

之字形层次遍历的本质仍是标准 BFS：单队列 + 层开始时快照queue.size()实现逐层切分；之字形的全部增量只在于一个按层取反的方向标记（以及可选的原地反转或 deque 出队方向控制）。官方解法用"null 占位 + 空层过滤"把空树、缺子节点等边界全部收敛进主循环，代码分支极少；deque 解法则展示如何用双向出队免去反转。掌握这两种形态后，32.1～32.3 及各类逐层聚合变体都可以用同一份循环框架快速改写。

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes