考研笔记

二叉树的遍历

遍历本身你会，这一节真正的考点是「由遍历序列还原树」——以及哪些组合还原不出来。

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个除外）都有一个直接前驱和直接后继。这句话是 5.3.2 线索二叉树 的出发点——先有「遍历序列上的前驱后继」，才有「把它存进空链域」的想法。

机制

四种遍历

遍历规则递归时访问根的时机
先序（NLR）访问根 → 先序遍历左子树 → 先序遍历右子树进入结点时
中序（LNR）中序遍历左子树 → 访问根 → 中序遍历右子树左子树回来时
后序（LRN）后序遍历左子树 → 后序遍历右子树 → 访问根右子树回来时
层次遍历自上而下、自左向右逐层访问—

三种深度优先遍历的区别只有「访问根」这一句话放在哪。 递归算法的时间复杂度均为 ，空间复杂度为 （ 为树高，即递归栈的深度）。

层次遍历需要借助一个队列：根结点入队 → 队头出队并访问 → 其左、右孩子依次入队 → 重复直到队空。队列，不是栈——这是与前三种遍历唯一的结构性差别。

flowchart TD
    N["访问根结点"] --> L["遍历左子树"] --> R["遍历右子树"]
    P["先序 NLR<br/>根 左 右"]
    I["中序 LNR<br/>左 根 右"]
    O["后序 LRN<br/>左 右 根"]
    LV["层次<br/>用队列"]

    classDef pre fill:#ffcdd2,stroke:#b71c1c
    classDef inn fill:#c8e6c9,stroke:#1b5e20
    classDef post fill:#e3f2fd,stroke:#1565c0
    classDef lvl fill:#fff9c4,stroke:#f57f17
    class P pre
    class I inn
    class O post
    class LV lvl
    class N,L,R inn

非递归遍历

中序非递归是最基础的一个：沿左链一路入栈到底 → 弹栈访问 → 转向该结点的右子树重复。先序非递归只需把「访问」提前到入栈时。后序非递归最麻烦，因为要区分「从左子树回来」还是「从右子树回来」，需要额外记一个 r 指针指向最近访问过的结点。

空间复杂度都是 ，与递归版本相同——栈的深度不会超过树高。

由遍历序列构造二叉树

三种可以唯一确定：

组合分割依据
先序 + 中序先序的第一个是根，在中序里把序列切成左右两段，递归
后序 + 中序后序的最后一个是根，其余同上
层序 + 中序层序的第一个是根；若存在左子树，层序的第二个一定是左子树的根；若存在右子树，层序中紧接着的下一个一定是右子树的根

三种都必须有中序。 中序的作用是唯一的：它是唯一能把「根的左边」和「根的右边」切开的序列。

边界辨析：

教材原文：「注意，先序序列、后序序列和层序序列的两两组合，无法唯一确定一棵二叉树。」 反例（图 5.15）：两棵不同的二叉树，先序序列都是 ，后序序列都是 ，层序序列都是 。 根源在 5.2.1 的那条区别 ②—— 只有一个孩子时，二叉树必须区分它是左是右，而这三种序列都记录不下这个信息，只有中序能。

教材给的例子（图 5.12）：先序 + 中序 。由先序知 为根；中序中 之前的 为左子树的中序序列， 为右子树的中序序列；再由先序知 是左子树的根、 是右子树的根，以此类推。

手算模板

由「先序 + 中序」还原：

  1. 先序取头作根。
  2. 在中序里找到这个根，左边全是左子树，右边全是右子树，记下两段的长度。
  3. 用长度把先序切成对应的两段（先序里紧跟根的那段是左子树）。
  4. 对两段递归。

由「后序 + 中序」还原： 后序取尾作根，其余相同。

由「层序 + 中序」还原： 层序从左往右逐个当根用；每确定一个根就在中序里切一刀，切出的两段各自到层序里去找最先出现的那个元素作为子树的根。

验算：还原完后，把树重新按第三种序列走一遍，与题目给的对上才算完。

边界

说法判断说明
「先序 + 后序可唯一确定二叉树」❌不能。反例： / 对应两棵树
「先序 + 层序可唯一确定」❌三种「非中序」序列两两组合都不行
「后序 + 层序可唯一确定」❌同上
「中序 + 任一种可唯一确定」✅中序是唯一能切开左右子树的序列
「层次遍历用栈」❌用队列
「非递归遍历的空间复杂度低于递归」❌都是
「后序非递归只需一个栈」⚠️还需一个指针记录最近访问过的结点，用来区分从左还是从右回来
「遍历的时间复杂度是 」❌，每个结点恰好访问一次
「二叉排序树的中序序列递增」✅见 7.3.1，且是充要判据
「中序序列相同的二叉树只有一棵」❌有很多棵——这正是不能只由中序还原的原因

口径差异：

算竞里遍历几乎只写递归（或显式栈做迭代），关心的是怎么在遍历中顺便算东西（子树大小、DP 值、时间戳）。 408 考的是「序列长什么样」和「由序列反推树」——一个是过程，一个是结果。 另外，「层序遍历」在算竞里就是 BFS，两边一致；但 408 会问「层序 + 中序能否唯一确定」这类信息量问题， 算竞完全不涉及。

对照速查

遍历序列特征用途
先序第一个是根复制树、判断树形
中序根把序列切成左右两半唯一能切左右的序列；BST 中序有序
后序最后一个是根求子树高度、释放树
层序按层从左到右求宽度、按层处理
组合能否唯一确定
先序 + 中序✅
后序 + 中序✅
层序 + 中序✅
先序 + 后序❌
先序 + 层序❌
后序 + 层序❌

考点

  • 三种含中序的组合可唯一确定，不含中序的两两组合都不行——本节最高频。
  • 由后序序列和树形构造一棵二叉树（2017、2023 命题追踪）。
  • 层次遍历用队列，其余三种用栈。
  • 时间 、空间 。
  • 后序非递归需要额外的「最近访问」指针。
  • 遍历序列上的直接前驱与直接后继——线索二叉树 的入口概念。

链接

反向链接