🌲 二叉树遍历:终极通关指南

核心心法(刻在脑子里)

三个字: 根、左、右 铁律: 无论什么序遍历,左边永远比右边先走!

  • 先序 (Preorder):根 → 左 → 右 (老大最先说话)
  • 中序 (Inorder):左 → 根 → 右 (老大中间说话)
  • 后序 (Postorder):左 → 右 → 根 (老大最后说话)

第一部分:看图推顺序(拆解法)

核心思想

不要试图一次性看穿整棵树!把大树当成小树,像剥洋葱一样,一层层套公式。

🛠️ 操作步骤:

  1. 找老大:找出当前这棵(小)树的根节点。
  2. 分左右:看这个根,左边有一坨什么,右边有一坨什么。
  3. 套公式:把“根、左、右”的顺序套进去。

📝 实战演练:

假设树形如下(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
  • 💡 技巧:求后序,就是一路向右下角狂奔(找右边的叶子),写完了再写根。

第二部分:看顺序画树(切蛋糕法)

必背口诀

  1. 后序找最后:后序遍历的最后一个字母,绝对是总根。
  2. 先序找最前:先序遍历的第一个字母,绝对是总根。
  3. 看图数个数:看着空壳图,数一数左边有几个圈,右边有几个圈。
  4. 回串切一刀:用数出来的个数,把序列切成两半。
  5. 对号入座:把切好的字母,分别扔进左边和右边的坑里,然后递归重复。

📝 实战演练:

已知:后序遍历为 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

🚀 考试秒杀技巧(选择题专用)

做选择题时,不需要全算出来,用以下三招直接排除错误选项:

  1. 看总根位置:
    • 先序的第一个字母 = 总根。
    • 后序的最后一个字母 = 总根。
    • 中序中,总根在中间(左边是左子树,右边是右子树)。
  2. 看局部位置:
    • 比如右子树只有一个节点 c。
    • 在先序(根左右)中,c 肯定在最后面。
    • 在后序(左右根)中,c 肯定在总根的前面。
  3. 结合图数圈:
    • 看看图里最左下角的叶子是谁,往往能直接锁定先序的第一个或后序的第一个。

终极防坑指南

遇到一大坨,先在草稿纸上用括号 [ ] 把它括起来,算完里面的,再跟外面的拼。永远不要跳步!

📌 补充:408 遍历序列唯一性铁律(无树形图时)

当题目没有给出二叉树的空壳形状图,只给你两个遍历序列让你还原二叉树时:

  1. 一定能唯一确定二叉树的组合(必须有中序!先序/后序/层序定根,中序分左右):
    • ✅ 先序 + 中序
    • ✅ 后序 + 中序
    • ✅ 层序 + 中序
  2. 不能唯一确定二叉树的组合:
    • ❌ 先序 + 后序(当存在度为 1 的节点时,无法区分剩下的子树到底是左子树还是右子树!)
    • 💡 重要考点(2015 / 2017 年 408 真题):虽然“先序 + 后序”不能唯一确定左右孩子,但可以唯一确定任意两个节点的祖先/后代关系!
      • 口诀:若节点 在先序中排在 前面,且在后序中排在 后面,则 必定是 的祖先!
      • 若两个节点在先序中呈现 ... a, b ...,在后序中呈现 ... b, a ...(紧挨着且顺序相反),说明 是 的父节点且 只有一个孩子 (无法确定 是左孩子还是右孩子,共有 种可能的二叉树, 为这种反转对的个数)。