二叉树的遍历
知识总结
二叉树的定义
每个节点最多有两个子节点（左子节点和右子节点）的树。
三种遍历方式
| 遍历方式 | 访问顺序 | 口诀 |
|---|---|---|
| 前序遍历 | 根→左→右 | 根左右 |
| 中序遍历 | 左→根→右 | 左根右 |
| 后序遍历 | 左→右→根 | 左右根 |
遍历示例
A
/ \
B C
/ \ \
D E F- 前序：A B D E C F
- 中序：D B E A C F
- 后序：D E B F C A
- 层序：A B C D E F
由遍历序列还原二叉树（初赛重点）
- 前序 + 中序 → 可以唯一确定二叉树
- 后序 + 中序 → 可以唯一确定二叉树
- 前序 + 后序 → 不能唯一确定（除非是满二叉树）
还原方法：
- 前序的第一个元素（或后序的最后一个元素）是根
- 在中序中找到根，左边是左子树，右边是右子树
- 递归处理左右子树
层序遍历
使用队列实现，逐层从左到右访问所有节点。