二叉树的层次遍历
看完你能说清遍历次序、写出队列实现、并算清每层边界
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
二叉树的层次遍历
看完你能说清遍历次序、写出队列实现、并算清每层边界
什么是「按层」访问
公司开大会前，主持人不会逮着谁叫谁，而是先请 CEO 层的几位，再请总监层，最后到员工层——一层一层点名，这就是按层访问的直觉。
CEO 层对应根节点层，逐级下属对应逐层子树
次序规则：自上而下、从左到右
图中标注了每个节点的访问序号：先标根，再逐层从左往右依次编号，跟着序号走一遍。
层次遍历 vs 深度优先遍历
都叫「遍历」，但先/中/后序走的是纵向路径，层次遍历走横向——方向不同，访问顺序完全不同。
- 沿一条分支走到底再回头，纵向推进
- 用递归或栈，靠函数调用深度实现
- 先/中/后序差异在根的访问时机
- 按层横向推进，逐层完整覆盖
- 用队列，先进先出保证层内顺序
- 不存在先/中/后之分，只有一种顺序
为什么递归不管用，队列登场
上一页我们看到：深度优先会一头扎到底，访问顺序和「按层」完全对不上。问题出在哪？深度优先靠递归，本质是栈——后进先出。而逐层访问需要的是先进先出，这正好是队列的脾气。
先排队的人先打饭，对应先入队的节点先被访问
算法流程：入队、出队、带娃
层次遍历的循环就三个动作：出队、访问、把孩子押进队列。
代码实现
用队列把「出队、带娃」翻译成代码，几行就能跑通层次遍历。
第6行建队列，第10行出队访问，第13、15行「带娃」——左先进右后进，正好保证从左到右的次序。
边界细节：空树与队列清空时机
上一页代码能跑通，但真正的坑都在边界：树一开始就是空的怎么办？while 循环为什么写 q.empty()？孩子入队前为什么要判空？这三处写错，程序立刻崩。
窗口没人排队（队列空）就下班结束，对应循环终止
完整实例逐步走
拿一棵具体的小树，逐轮追踪队列状态与出队访问次序。
自测：写出遍历序列
二叉树：根为 1，左孩子 2、右孩子 3；2 的左孩子 4、右孩子 5；3 只有右孩子 6。层次遍历序列是？
要点收束
- ✓按层访问=自上而下、从左到右的次序
- ✓递归天然走深度，层次次序须靠队列 FIFO 维持
- ✓核心循环三步：出队访问、孩子按左先右后入队
- ✓空树直接返回，队列为空才是终止条件
- ✓序列唯一可验证，是检验实现 correct 的标尺
课后思考
三个问题，先自己想，再对照参考答案。
参考答案从队列先进先出改为栈后进先出，出队顺序颠倒，某一层的右子树会先于左子树被访问，同层从左到右的次序被破坏。想想它退化成了哪种遍历。
参考答案抓住「队列长度=当前层节点数」这个事实：每轮循环先记录 size，只出队 size 个节点，它们恰好是同一层。出队时把孩子入队，正好留给下一层。
参考答案队列仍负责分层，但奇偶层输出方向交替即可，多数场景无需换数据结构。若用双端队列在两端出入队，可以进一步实现真正的反向收集，想想两者的区别。