🌲 二叉树遍历:终极通关指南
核心心法(刻在脑子里)
三个字: 根、左、右 铁律: 无论什么序遍历,左边永远比右边先走!
- 先序 (Preorder):根 → 左 → 右 (老大最先说话)
- 中序 (Inorder):左 → 根 → 右 (老大中间说话)
- 后序 (Postorder):左 → 右 → 根 (老大最后说话)
第一部分:看图推顺序(拆解法)
核心思想
不要试图一次性看穿整棵树!把大树当成小树,像剥洋葱一样,一层层套公式。
🛠️ 操作步骤:
- 找老大:找出当前这棵(小)树的根节点。
- 分左右:看这个根,左边有一坨什么,右边有一坨什么。
- 套公式:把“根、左、右”的顺序套进去。
📝 实战演练:
假设树形如下(Obsidian 会自动渲染出下图):
graph TD A((a)) --> B((e)) A --> C((c)) B --> D((d)) B --> E((b)) D --> F((f)) style A fill:#f9f,stroke:#333,stroke-width:2px style C fill:#bbf,stroke:#333,stroke-width:2px
1. 求【先序】(根 → 左 → 右)
- 整棵树:根是
a,左边一坨[e, d, f, b],右边一坨[c]。- 套公式:
a+[左边]+c
- 套公式:
- 拆左边:根是
e,左边[d, f],右边[b]。- 套公式:
e+[d, f]+b
- 套公式:
- 拆
[d, f]:根是d,左边[f],右边空。- 套公式:
d+f+ 空
- 套公式:
- 拼起来:
a+ (e+d+f+b) +c=aedfbc - 💡 技巧:求先序,就是一路向左下角狂奔,碰到谁写谁,没左路了再找右路。
2. 求【中序】(左 → 根 → 右)
- 整棵树:
[左]+a+c - 拆左边:
[d, f]+e+b - 拆
[d, f]:f+d+ 空 - 拼起来:(
f+d+e+b) +a+c=f, d, e, b, a, c - 💡 技巧:求中序,就像“投影法”。把所有节点垂直往下拍扁,从左到右的顺序就是中序。
3. 求【后序】(左 → 右 → 根)
- 整棵树:
[左]+c+a - 拆左边:
[d, f]+b+e - 拆
[d, f]:f+ 空 +d - 拼起来:(
f+d+b+e) +c+a=f, d, b, e, c, a - 💡 技巧:求后序,就是一路向右下角狂奔(找右边的叶子),写完了再写根。
第二部分:看顺序画树(切蛋糕法)
必背口诀
- 后序找最后:后序遍历的最后一个字母,绝对是总根。
- 先序找最前:先序遍历的第一个字母,绝对是总根。
- 看图数个数:看着空壳图,数一数左边有几个圈,右边有几个圈。
- 回串切一刀:用数出来的个数,把序列切成两半。
- 对号入座:把切好的字母,分别扔进左边和右边的坑里,然后递归重复。
📝 实战演练:
已知:后序遍历为 f, d, b, e, c, a,树形为 6 个圆圈(左4右1)。
- 第一步(找总根):后序最后是
a。填在最上面。 - 第二步(切第一刀):去掉
a,剩f, d, b, e, c。看图,左边 4 个圈,右边 1 个圈。- 切给左边:
f, d, b, e - 切给右边:
c(把c填入右边那个圈)
- 切给左边:
- 第三步(解决左边):当前字母
f, d, b, e。最后一个是e,所以e是这一小坨的根。- 看图,
e左边有 2 个圈,右边有 1 个圈。 - 切给左边:
f, d - 切给右边:
b(把b填入e右下的圈)
- 看图,
- 第四步(解决最后两个圈):当前字母
f, d。最后一个是d,所以d是根。- 把
d填入e左下的圈。 - 剩下的
f填入d下面的圈。
- 把
最终还原图如下:
graph TD A((a)) --> B((e)) A --> C((c)) B --> D((d)) B --> E((b)) D --> F((f)) style A fill:#f9f,stroke:#333,stroke-width:2px style C fill:#bbf,stroke:#333,stroke-width:2px
🚀 考试秒杀技巧(选择题专用)
做选择题时,不需要全算出来,用以下三招直接排除错误选项:
- 看总根位置:
- 先序的第一个字母 = 总根。
- 后序的最后一个字母 = 总根。
- 中序中,总根在中间(左边是左子树,右边是右子树)。
- 看局部位置:
- 比如右子树只有一个节点
c。 - 在先序(根左右)中,
c肯定在最后面。 - 在后序(左右根)中,
c肯定在总根的前面。
- 比如右子树只有一个节点
- 结合图数圈:
- 看看图里最左下角的叶子是谁,往往能直接锁定先序的第一个或后序的第一个。
终极防坑指南
遇到一大坨,先在草稿纸上用括号
[ ]把它括起来,算完里面的,再跟外面的拼。永远不要跳步!
📌 补充:408 遍历序列唯一性铁律(无树形图时)
当题目没有给出二叉树的空壳形状图,只给你两个遍历序列让你还原二叉树时:
- 一定能唯一确定二叉树的组合(必须有中序!先序/后序/层序定根,中序分左右):
- ✅ 先序 + 中序
- ✅ 后序 + 中序
- ✅ 层序 + 中序
- 不能唯一确定二叉树的组合:
- ❌ 先序 + 后序(当存在度为 1 的节点时,无法区分剩下的子树到底是左子树还是右子树!)
- 💡 重要考点(2015 / 2017 年 408 真题):虽然“先序 + 后序”不能唯一确定左右孩子,但可以唯一确定任意两个节点的祖先/后代关系!
- 口诀:若节点 在先序中排在 前面,且在后序中排在 后面,则 必定是 的祖先!
- 若两个节点在先序中呈现
... a, b ...,在后序中呈现... b, a ...(紧挨着且顺序相反),说明 是 的父节点且 只有一个孩子 (无法确定 是左孩子还是右孩子,共有 种可能的二叉树, 为这种反转对的个数)。