二叉树遍历 · 单步演示
前序遍历
先访问根，再前序遍历左子树，最后前序遍历右子树。访问顺序就是「从上往下、先左后右」地第一次碰到每个结点的顺序。
调用栈（底 → 顶）（空）
前序序列（空）
步 001 / 057前序遍历：先访问根，再左子树，最后右子树。
键盘：← → 单步，空格 播放/暂停（先点一下演示区）。
伪代码 · 当前行高亮
遍历(node)：if node 为空：return访问 node遍历(node.left)遍历(node.right)
变量
| node | 空 |
|---|---|
| 递归深度 | 0 |
| 已输出 | [] |
复杂度
| 最好情况 | O(n) |
|---|---|
| 平均情况 | O(n) |
| 最坏情况 | O(n) |
| 额外空间 | O(h) |
每个结点恰好访问一次。额外空间是递归调用栈，深度等于树高 h：平衡树约 log₂n，退化成一条链时是 n。
要点
- 复制一棵树、把树写成层层缩进的目录时，用的就是前序。
- 前序序列的第一个元素一定是根。
常见错误
只有前序序列无法唯一还原一棵树；前序加中序（且值不重复）才可以。