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

本篇技术指南基于 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 做反转。三题的递进关系可以概括为：

题目	输出结构	与上一题的差异
32.1	一维 ArrayList<Integer>	单队列 + cnt 逐层遍历
32.2	二维 ArrayList<ArrayList<Integer>>	每层单独收集为一个子列表
32.3	二维（奇数层反转）	增加 reverse 标记，按层奇偶翻转

官方解法：队列 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：

维度	官方解法（BFS + reverse）	deque 解法
时间	O(n)，遍历一次 + 各层原地反转总 O(n)	O(n)，无反转
空间	O(n)，队列最坏持有 O(n) 节点（含 null 占位）	O(n)，队列最坏持有 O(n) 节点
递归栈深度	无（迭代实现）	无（迭代实现）

迭代实现也顺带规避了树高度 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 及各类逐层聚合变体都可以用同一份循环框架快速改写。