二叉树遍历 · 单步演示
层序遍历
从根开始一层一层往下，每层从左到右访问。用一个队列：出队一个结点就访问它，再把它的孩子按左、右顺序入队。
队列（头 → 尾）（空）
层序序列（空）
步 001 / 024层序遍历：一层一层从左往右访问，靠一个队列记住「下一个该看谁」。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
if root 为空：returnQ ← [root]while Q 非空node ← Q 出队；访问 nodeif node.left 存在：left 入队if node.right 存在：right 入队
变量
| node | — |
|---|---|
| 队列长度 | 0 |
| 已输出 | [] |
复杂度
| 最好情况 | O(n) |
|---|---|
| 平均情况 | O(n) |
| 最坏情况 | O(n) |
| 额外空间 | O(w) |
每个结点入队、出队各一次。队列里最多同时放着一层的结点，w 是树最宽一层的结点数，完全二叉树的最底层约 n/2。
要点
- 层序遍历就是树上的广度优先搜索。
- 想按层分组输出时，在每层开始前记下当时的队列长度即可。
常见错误
用栈代替队列，访问顺序就变成了另一种深度优先，而不是按层。