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

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 ArrayListArrayListInteger Print(TreeNode pRoot) { ... }返回值是每层一个子列表的二维结构。这一点很关键它决定了算法必须按层分组而不像 32.1 那样把所有节点拍平成一个列表。前置基础单队列逐层遍历的通用骨架32.3 并不是凭空出现的技巧它建立在同系列前两题之上32.1 从上往下打印二叉树 与 32.2 把二叉树打印成多行。仓库中 32.1 的题解给出了层次遍历最核心的思想见 32.1 题解不需要使用两个队列分别存储当前层的节点和下一层的节点因为在开始遍历一层的节点时当前队列中的节点数就是当前层的节点数只要控制遍历这么多节点数就能保证这次遍历的都是当前层的节点。这个层内计数技巧是整组题目的骨架每轮外层循环开始时先记录queue.size()这就是当前层的节点个数cnt内层循环恰好弹出cnt个节点弹出时把它们的子节点入队——子节点全部属于下一层因此下一轮queue.size()恰好等于下一层节点数无需额外数组、无需当前层队列 下一层队列的双队列结构。32.1 的输出是所有节点拍平的一维列表32.2 只是把每层的收集结果list独立存进结果二维数组32.3 则在此基础上多了一步——对奇数层的list做反转。三题的递进关系可以概括为题目输出结构与上一题的差异32.1一维ArrayListInteger单队列 cnt逐层遍历32.2二维ArrayListArrayListInteger每层单独收集为一个子列表32.3二维奇数层反转增加reverse标记按层奇偶翻转官方解法队列 BFS Collections.reverse下面是 32.3 题解 给出的完整解法仓库原文可直接复制到牛客对应题目运行public ArrayListArrayListInteger Print(TreeNode pRoot) { ArrayListArrayListInteger ret new ArrayList(); QueueTreeNode queue new LinkedList(); queue.add(pRoot); boolean reverse false; while (!queue.isEmpty()) { ArrayListInteger 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保持空列表——空树直接返回[]无需单独分支。2cnt在层开始时刻快照int cnt queue.size()是层遍历的锚点。注意此刻队列中混有上一轮入队的null某节点缺失的左/右子节点也会以null入队cnt统计的是占位数而非实际节点数内层循环恰好消费完当前层全部占位下一轮queue.size()自然就是下一层的占位数逐层推进直到队列耗尽。3null 容错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 双向队列免反转上面的解法先按左到右收集再原地反转直观但每层要额外走一遍。也可以从访问顺序入手让队列本身按打印方向出队——用DequeLinkedList同时实现了Deque和Queue偶数层从队首出队、子节点追加到队尾奇数层从队尾出队、子节点插到队头。这样每层的line天然就是打印顺序省掉Collections.reversepublic ArrayListArrayListInteger Print(TreeNode pRoot) { ArrayListArrayListInteger ret new ArrayList(); if (pRoot null) return ret; DequeTreeNode deque new LinkedList(); deque.offer(pRoot); boolean leftToRight true; while (!deque.isEmpty()) { int size deque.size(); ArrayListInteger 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 解法展示对双向队列的驾驭。关键细节与易错点结合仓库原题解的写法梳理实现该题时最容易踩坑的四处反转时机必须在整层收集完后统一reverse而不是出队时就决定方向前者依赖队列内层内节点天然从左到右这一不变式。空树返回接口要求返回层的列表空树应返回空列表[]而非null。官方解法通过 null 占位 空层过滤天然达成deque 解法则需要显式if (pRoot null) return ret。cnt与size的关系官方解法中cnt包含 null 占位是占位规模deque 解法中size是真实节点规模。混用两套语义例如 deque 解法里入队不判空会破坏逐层推进的正确性。单节点/斜树退化链状树每层只有一个真实节点方向翻转对单元素层无可见效果但reverse标记仍须逐层取反不能因这层只有一个节点而提前终止或跳过翻转否则后续层方向错乱。复杂度小结设树有 n 个节点、高度为 h维度官方解法BFS reversedeque 解法时间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 仓库内建议按如下顺序串起学习闭环剑指 Offer 题解 - 目录 的树章节定位 32.1 → 32.2 → 32.3 三连题体会同一 BFS 骨架的三次演进Leetcode 题解 - 树 中的层次遍历小节补充每层节点平均数得到左下角节点等基于同一队列模式的题目巩固层内计数的熟练度。总结之字形层次遍历的本质仍是标准 BFS单队列 层开始时快照queue.size()实现逐层切分之字形的全部增量只在于一个按层取反的方向标记以及可选的原地反转或 deque 出队方向控制。官方解法用null 占位 空层过滤把空树、缺子节点等边界全部收敛进主循环代码分支极少deque 解法则展示如何用双向出队免去反转。掌握这两种形态后32.132.3 及各类逐层聚合变体都可以用同一份循环框架快速改写。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考