一、起源:从线性结构到层次结构

1.1 线性结构在层次关系上的不足

数组与链表描述的是「一个元素至多有一个前驱、一个后继」的关系,见 数组与链表。这种一对一的关系能够表达序列,却不能表达包含与从属。

层次关系的特征是「一对多」:一个整体由若干部分组成,每个部分又可以继续细分。文件系统、组织架构、算术表达式、语法结构、分类体系都属于这一类。用线性结构表达它,只有两种办法,代价都很明显。

把层次压平成序列。例如用「先根序列」记录路径,每个元素前面附带层号或父节点下标。这种表示可以存储,但层次信息被降级为附加字段,任何与层次相关的操作(求祖先、求子树、求深度)都需要重新扫描整个序列,无法利用关系本身的结构。

用引用字段显式编码关系。例如在数组之外为每个元素记录一个父节点下标。这实际上已经在构建非线性的关系,只是没有把它作为独立的逻辑结构看待。一个父子关系的集合,其形态就是树。

树之所以独立于线性表,在于关系的存储方式发生了变化:线性表中位置由下标或前驱指针唯一确定,树中每个节点需要保存多个后继的入口。这一差别带来的直接后果是——定位不再是「走固定步数」,而是「在每一步选择走哪个分支」,选择过程本身可以携带比较信息。

1.2 分治查找对结构的要求

在有序数组中查找一个元素,二分查找每次比较可以把候选范围缩小一半,代价为 O(log n)。它能够这样做的前提有两个:

  1. 元素有序,比较结果给出了「目标在左半还是右半」的信息。
  2. 中间位置可以 O(1) 到达,即元素按位置连续存储。

把二分查找的过程画出来,每一步的「中间元素」构成一个节点:第一次比较的中间元素是根,左半区间的中间元素是左子节点,右半区间是右子节点。这棵描述比较路径的判定树,形态就是一棵二叉搜索树。

于是得到一条直接的推论:如果能把「每次比较后确定性地走到下一半」这件事从下标算术中解放出来,用显式的链接表示,那么查找代价就由比较次数决定,而与元素的物理位置无关。这正是树形结构在查找上的价值——它把「有序」与「可定位」这两件事分开存储:有序性保存在节点之间的位置关系里,定位方式保存在每一步的分支选择里。

代价随之出现。二叉搜索树不再需要搬移元素(插入删除只改指针),但它放弃了数组的 O(1) 随机访问,并且查找代价不再是固定的 ⌊log₂n⌋,而是取决于树的形状——形状又由插入顺序决定。这一取舍贯穿整篇内容。

1.3 对数级查找的直觉

从信息量角度可以看清 O(log n) 的来源。每次比较只有「小」「等」「大」三种结果,在节点值与目标不相等时实际只有两种有效走向,因此一次比较最多区分两种可能。要在 n 个候选元素中确定一个,至少需要 ⌈log₂n⌉ 次这样的二分决策。二分查找达到这一下界,二叉搜索树的每条查找路径也是同样长度的决策链。

n = 1 000          二分决策次数约 10
n = 1 000 000      二分决策次数约 20
n = 1 000 000 000  二分决策次数约 30

规模每扩大一倍,代价只增加一次比较。这条增长曲线的现实意义是:对数级结构在数据量增长几个数量级后仍然可用,而线性结构早已不可用。复杂度的量级对照与增长趋势的完整讨论见 复杂度与算法分析。

把这棵「决策树」的每个节点限制为最多两个子节点,得到二叉树;允许每个节点有多个子节点(多路),则一次比较可以区分更多走向,树高进一步下降。为磁盘这类以块为单位读取的存储设计索引时,后者的收益更大,原因在第三节 5.4 节展开。

1.4 递归结构与递归算法的天然契合

树是递归定义的:

  • 空树是一棵二叉树;
  • 非空二叉树由根节点、左子树、右子树构成,左子树与右子树各自也是二叉树。

定义的递归性决定了处理方式的递归性。一个作用于二叉树的算法,只要能做到「对根做常数级处理」与「把同样的问题交给左右子树」,就自动覆盖了整棵树。这是绝大多数树算法只有三五行代码的原因,也是树成为递归思维最佳训练场的原因。

递归执行时,每进入一层子树就压入一个栈帧,返回时弹出。栈帧中保存的「当前处理到哪个节点、下一步该处理哪边」恰好对应「已经走过的祖先路径」与「尚未处理的兄弟子树」。因此树的递归遍历与显式栈的迭代遍历在状态上是同构的:递归调用栈就是遍历所需的那个结构,只是它由运行时维护。递归与栈的对应关系、调用栈的构成见 栈与队列。

1.5 与链式存储的承接

树的链式表示与链表的节点在结构上同源:都是「数据域 + 指向后继的引用」,区别只是后继的个数从一个变为两个(二叉树)或多个(多叉树)。因此前一篇关于节点开销、指针追逐、缓存局部性、递归深度限制的结论在树上同样成立,只是「不能按下标定位」这一约束在树上演化为「不能按层序位置直接定位」,而节点数的增长方式从线性变为指数——高度为 h 的满二叉树有 2^h − 1 个节点。链式存储与指针操作的基础见 数组与链表,抽象数据类型与存储实现的分离见 抽象数据类型(ADT)。

二、原理

1. 基本术语与性质

1.1 术语

术语 含义
节点 树的基本单位,保存数据以及指向子节点的引用
根节点 没有父节点的唯一节点
父节点与子节点 若从节点 u 到 v 有一条边且 u 在上方,则 u 是 v 的父节点,v 是 u 的子节点
兄弟节点 同一个父节点的若干子节点
度 一个节点的子节点个数;二叉树的度取值不超过 2
叶子节点 度为 0 的节点,也称终端节点
分支节点 度不为 0 的节点,也称非终端节点
层次 从根开始计数的层号,根为第 1 层,其子节点为第 2 层,依此类推
深度 从根到该节点的层数,根的深度为 1
高度 从该节点到其子树中最深叶子的层数,叶子节点的高度为 1
树的高度 根节点的高度,空树的高度定义为 0
路径与路径长度 节点之间的边构成的序列;路径长度为经过的边数
祖先与后代 从根到该节点路径上的所有节点为该节点的祖先;反向为后代
子树 以某节点为根,包含其全部后代的集合

关于口径需要先说明:不同教材对根所处的层号(1 或 0)与高度的定义(节点数或边数)有差异,两者相差一个常数,不影响任何复杂度结论。本文统一采用「根为第 1 层、叶子高度为 1、空树高度为 0」,即高度与深度均按节点数计。阅读其他资料时先确认其约定,是避免公式套错的常用做法。

1.2 节点数的关系

设度为 0、1、2 的节点数分别为 n₀、n₁、n₂,节点总数为 n,则

n = n₀ + n₁ + n₂

边数:树中除根以外的每个节点恰有一条与父节点相连的边
      边数 = n − 1

边数也可按「每个节点贡献其度数条边」统计
      边数 = 0·n₀ + 1·n₁ + 2·n₂ = n₁ + 2n₂

两式联立:n₀ + n₁ + n₂ − 1 = n₁ + 2n₂
      得: n₀ = n₂ + 1

这个等式是二叉树最常用的结论之一,它只用到「除根外每个节点只有一个父节点」这一结构性事实,与树的形状无关。两条直接推论:

  • 叶子数永远比双子节点数多 1。叶子数为 n₀ 时,双子节点数必然是 n₀ − 1,与 n₁ 无关。
  • 节点总数 n = 2n₀ + n₁ − 1。因此节点总数与叶子节点数之间只差 n₁ 这一项,而 n₁ 的取值受限(见 1.4 节)。

1.3 高度与层上的节点数

按层次逐层统计最多个数:

第 1 层(根)    最多 1 个节点 = 2⁰
第 2 层          最多 2 个节点 = 2¹
第 3 层          最多 4 个节点 = 2²
...
第 i 层          最多 2^(i−1) 个节点

几何级数求和给出高度与节点总数的关系:

高度为 h 的二叉树,节点总数最多:
    n ≤ 2⁰ + 2¹ + ... + 2^(h−1) = 2^h − 1

高度为 h 的二叉树,节点总数最少:
    每层至少 1 个节点,n ≥ h

反向解出 n 个节点的二叉树的高度范围:

n ≤ 2^h − 1    ⟹    2^h ≥ n + 1    ⟹    h ≥ ⌈log₂(n + 1)⌉

高度下界 ⌈log₂(n + 1)⌉(形态最紧凑)
高度上界 n(每层只有一个节点,即一条链)

叶子数也有同样的界:高度为 h 的二叉树最多有 2^(h−1) 个叶子(最下面一层填满),最少有 1 个叶子(一条链)。这两个界分别对应后面提到的「完全平衡」与「完全退化」两种极端形态。

1.4 满二叉树与完全二叉树

满二叉树:每一层的节点数都达到最大值。高度为 h 的满二叉树有

节点总数  n = 2^h − 1
叶子节点  n₀ = 2^(h−1)
非叶子    2^(h−1) − 1
校验       n₀ = n₂ + 1  →  2^(h−1) = (2^(h−1) − 1) + 1

完全二叉树:节点按层序编号后与同高度满二叉树的编号 1..n 一一对应。直观描述是「除最后一层外每层都填满,最后一层的节点集中在左侧,中间不断开」。它的结构性质如下。

n 个节点的完全二叉树,高度为:
    h = ⌊log₂n⌋ + 1        (根为第 1 层的口径)

度为 1 的节点至多 1 个:
    若 n 为奇数,n₁ = 0
    若 n 为偶数,n₁ = 1

由 n = 2n₀ + n₁ − 1 得:
    n 为奇数:n₀ = (n + 1) / 2
    n 为偶数:n₀ = n / 2
    合并写作 n₀ = ⌈n / 2⌉

「度为 1 的节点至多 1 个」这一点的推理是:完全二叉树中最多只有一个节点可能只带左子节点;若出现第二个只有左子节点的节点,说明中间的某层出现了空缺,与完全二叉树的定义矛盾。

完全二叉树的重要性有两点。它是高度最小的二叉树形态,n 个节点的高度为 ⌊log₂n⌋ + 1,达到前述高度下界;它的编号规律使父子关系可以由下标算术给出,因此可以完全用数组存储而不需要任何引用字段(见 2.2 节)。二叉堆正是「完全二叉树 + 数组存储 + 堆序性质」的组合。

1.5 小结表

结论 表达式 前提
叶子与双子节点数 n₀ = n₂ + 1 任意二叉树
第 i 层最多节点数 2^(i−1) 根为第 1 层
高度 h 最多节点数 2^h − 1 满二叉树
高度 h 最少节点数 h 每层一个节点
n 个节点高度下界 ⌈log₂(n + 1)⌉ 完全二叉树达到
n 个节点高度上界 n 单支树
完全二叉树高度 ⌊log₂n⌋ + 1 根为第 1 层
完全二叉树叶子数 ⌈n / 2⌉ —

2. 存储表示

2.1 链式表示

链式表示把每个节点独立分配,用引用串联。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

三处取舍需要明确。

是否需要父指针。加上 TreeNode parent 字段后,从任意节点向根回溯不再需要从根重新遍历,中序前驱与后继可以在均摊 O(1) 内求出,删除操作也不必再维护「父节点的子引用」这一返回值的传递路径。代价是每个节点多一个引用,且任何修改结构的操作都必须同时维护两个方向——树的代码中「双方向不一致」与链表中只更新一条 next 属于同一类错误。判断依据是操作模式:只需要自顶向下遍历时不要父指针,依赖「从节点向根」的操作(求深度、求祖先、迭代器双向移动)时加上它更划算。

是否需要空节点哨兵。用一个共享的空节点(NIL)代替 null 可以消除大量的判空分支,但也会引入「哨兵是否被共享」的判断成本。二叉树中 null 的语义清晰,因此主流实现直接使用 null;红黑树等需要区分「叶子」与「内部节点」的实现才会引入 NIL 节点。

是否需要额外的层级信息。节点的子树规模、高度、颜色等字段属于平衡树维护的辅助信息,普通二叉搜索树不保存,因为一旦保存就必须在每次结构变化时同步更新。同步逻辑遗漏是树实现中最隐蔽的缺陷来源。

链式表示的代价与链表相同:每个节点有对象头与两个引用字段的空间开销,节点在堆中分散分布导致遍历时缓存命中率低,且无法按位置定位。对 100 万节点的树,仅引用字段与对象头就占用数十 MB,估算方式见 数组与链表 的节点开销一节。

2.2 数组表示

完全二叉树的编号规律可以直接转成下标算术。

按层序从 0 开始编号,节点 i 的:

父节点        ⌊(i − 1) / 2⌋        (i > 0)
左子节点      2i + 1
右子节点      2i + 2
是否为叶子    2i + 1 > n − 1  即  i > ⌊n/2⌋ − 1
最后一个非叶节点下标   ⌊n / 2⌋ − 1
所在层(从 1 开始)  ⌊log₂(i + 1)⌋ + 1

三个性质使数组表示在完全二叉树上优于链式表示:

  1. 没有引用字段,空间利用率最高,只有数据本身;
  2. 下标算术代替指针追逐,父子访问是相邻或按公式跳转,缓存局部性远好于链式;
  3. 层序即数组顺序,不需要队列即可按层处理。

代价出现在形态不完整时。数组必须为「按完全二叉树编号后可能出现的所有位置」预留槽位,因此

完全二叉树:n 个节点只需 n 个槽位
单支链(每层只有一个节点):n 个节点需要 2ⁿ − 1 个槽位
n = 30 的链:2³⁰ − 1 ≈ 10⁹ 个槽位

也就是说,数组表示的空间代价由树高决定(O(2^h)),链式表示由节点数决定(O(n))。只有在树形接近完全二叉树(高度为 O(log n))时,数组表示才是高效的。任意形态的二叉搜索树因此一律采用链式表示,而堆、线段树这类结构性态可控的结构才使用数组。

第三个差异是扩容。数组表示需要预知规模或动态扩容,扩容时整棵树重新分配;链式表示逐个节点分配,不受整体容量约束。这也说明数组表示适用于节点数固定或可上界估计的场景。

2.3 线索二叉树

n 个节点的二叉树共有 2n 个引用字段,其中被实际使用的只有 n − 1 个(每条边一个),n + 1 个引用是空的。线索二叉树的思想是把这些空引用利用起来,指向遍历次序中的前驱或后继。

节点字段:left, right, ltag, rtag
    ltag = 0:left 指向左孩子
    ltag = 1:left 指向中序前驱
    rtag = 0:right 指向右孩子
    rtag = 1:right 指向中序后继

最常用的形态是中序线索二叉树:
    沿着 rtag = 1 的引用可以直接走到中序后继,不需要栈,也不需要父指针

线索化的收益是把中序遍历的额外空间从 O(h) 降到 O(1),并且支持从任意节点出发的后继查找。代价与限制同样明确:

  • 每个节点多出两个标志位(或复用引用字段的低位),结构与存储开销上升;
  • 插入与删除节点后线索需要重新维护,维护逻辑比普通遍历更易出错;
  • 线索形态与遍历次序绑定,为中序建立的线索无法用于前序或后序。

工程实践中线索二叉树的直接使用较少,但它的思路在现代实现中仍有对应:莫里斯遍历(见 3.4 节)临时利用空引用构造线索,用完即恢复,相当于「不持久化、按需建立」的线索化;TreeMap 之类的有序映射则用父指针与辅助字段替代线索,达到同样的「免栈遍历」效果。线索二叉树的价值更多在于说明「空引用本身携带信息位」这一视角。

3. 遍历

3.1 四种遍历的定义与用途

遍历是「每个节点恰好访问一次」的过程。二叉树的遍历按「根、左子树、右子树」三者的处理次序命名,根在左右之间处理的层次展开方式单独构成一种。

前序(先序)  根 → 左子树 → 右子树     NLR
中序          左子树 → 根 → 右子树     LNR
后序          左子树 → 右子树 → 根     LRN
层序          按层从上到下,同层从左到右   BFS

四种次序各自的适用场景可以由「什么时候需要用到根的信息」推出:

遍历 访问根的时机 典型用途
前序 进入子树时立刻访问 复制树(先造根再接子树)、序列化、打印结构、表达式树还原前缀表达式
中序 左子树处理完之后 二叉搜索树取有序序列、校验 BST、线索化、表达式树还原中缀表达式
后序 左右子树都处理完之后 释放节点(先释放子树再释放根)、计算子树统计量(高度、节点数、直径)、表达式树求值
层序 按距离根的层数 按层输出、求树宽、求最小深度、找最近邻层级、判断完全二叉树

判断依据可以概括为:需要先拿到子树的计算结果再处理根,用后序;需要沿路径自顶向下传递信息,用前序;需要利用有序性,用中序;问题以「距离」而非「深度方向」为单位,用层序。

3.2 递归实现与调用栈

void preorder(TreeNode node, List<Integer> res) {
    if (node == null) return;          // 终止条件:空树,对应空树的递归定义
    res.add(node.val);                 // 根
    preorder(node.left, res);          // 左子树
    preorder(node.right, res);         // 右子树
}

中序与后序只需把 res.add 一行移动到两次递归之间或之后。三者的代码骨架完全相同,区别只在「处理根」与「递归子树」的相对次序。

递归的执行过程与栈帧的对应关系是理解非递归实现的基础:

递归执行 inorder(root):
    push 帧(root) → 递归 inorder(root.left)
        push 帧(root.left) → 递归 inorder(root.left.left)
            ... 一直压栈直到空节点返回
        弹出并处理栈顶(最左节点)
        递归 inorder(最左.right) → 压栈 new 帧
    弹出并处理栈顶(root)
    递归 inorder(root.right) → 压栈

栈中保存的是「已到达但尚未处理完的节点」,其自底向上的顺序恰好是从根到当前节点的路径。因此递归遍历的空间代价等于树高:每深入一层左右子树各挂一个待返回的帧,栈深度为 O(h)。平衡树上为 O(log n),退化为链时是 O(n)——这是第 6 节退化问题在空间上的直接后果。递归深度限制与栈溢出的关系见 栈与队列。

3.3 非递归实现

非递归实现把运行时维护的调用栈换成显式栈,收益有三点:递归深度不再受线程栈容量约束(栈帧转移到堆上,可容纳的深度由堆大小决定);可以在遍历中途暂停、恢复、插入控制逻辑;可以精确控制每个节点何时被处理,这在前序与后序的变体中很有用。

前序:最简单的形式是先压右子节点再压左子节点,保证左子节点先出栈。

List<Integer> preorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.add(node.val);
        if (node.right != null) stack.push(node.right);   // 先压右,后出栈
        if (node.left != null)  stack.push(node.left);
    }
    return res;
}

中序:不能沿用「入栈即访问」的形式,因为根的访问必须排在左子树之后。做法是沿左链一路压栈,弹出时访问并转向右子树。

List<Integer> inorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {          // 一路向左,把路径压栈
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();             // 栈顶即当前子树中最左的未访问节点
        res.add(cur.val);
        cur = cur.right;               // 转向右子树,下一轮继续压左链
    }
    return res;
}

这段代码中「当前节点为空但栈非空」表示刚从某个右子树返回,需要弹出上层节点继续;两个条件缺一不可,把循环条件写成单个 cur != null 会漏掉右子树存在的情况。

后序:难点在于根必须在左右子树之后访问,而在弹出栈顶时无法区分「第一次到达」与「已处理完子树后返回」。两种常用解法:

// 解法一:按「根 → 右 → 左」入栈,结果逆序即为后序
List<Integer> postorder(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val);        // 头插,等价于最后整体反转
        if (node.left != null)  stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}
解法二:标记法(也称双栈或染色法)
    栈中存放 (节点, 是否已处理子树) 二元组
    第一次弹出:标记为已处理,再把该节点与右子节点、左子节点重新压栈
    第二次弹出:此时左右子树都已处理完,可以访问
    代价是每个节点入栈两次,栈容量上限约为 2h

两种解法都不需要保存「上一个访问的节点」,比「记录 lastVisited 判断是否从右子树返回」的写法更易读。

显式栈的容量。栈中元素个数不超过树高(标记法会到两倍),因此在退化为链的树上,显式栈同样会增长到 O(n)。用显式栈解决了系统调用栈的溢出问题,但没有改变空间量级。

3.4 莫里斯遍历

莫里斯(Morris)遍历把空间降到 O(1):不借助栈,而是临时利用叶子节点空闲的右引用构造回到当前节点的线索,用完再拆除。

中序莫里斯遍历的规则(当前节点为 cur):
    若 cur 无左子树 → 访问 cur,cur 转向右子树
    若 cur 有左子树:
        找到 cur 左子树中的最右节点,记为 pred(即 cur 的中序前驱)
        若 pred.right 为空 → 建立线索 pred.right = cur,cur 转向左子树
        若 pred.right 已指向 cur → 拆除线索(恢复为空),访问 cur,cur 转向右子树
List<Integer> morrisInorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            res.add(cur.val);
            cur = cur.right;
        } else {
            TreeNode pred = cur.left;
            while (pred.right != null && pred.right != cur) {
                pred = pred.right;
            }
            if (pred.right == null) {
                pred.right = cur;      // 建立线索:从最右节点回到 cur
                cur = cur.left;
            } else {
                pred.right = null;     // 拆除线索,恢复原树结构
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

关于代价需要区分两种口径:

  • 额外空间为 O(1),不需要栈;
  • 时间为 O(n),但不是每节点 O(1)。每个节点的左子树的最右链会被走两遍(建立线索一遍、拆除一遍),因此常数比递归版本高,总访问次数约为 2n。

莫里斯遍历的核心限制是在遍历过程中会临时修改树结构,因此不适用于并发读取,也不适用于任何需要在遍历期间保持树不可见的场景。前序遍历的莫里斯版本只需调整「访问」语句的位置;后序的莫里斯版本需要借助临时反转,实现复杂度显著上升,一般不做要求。

3.5 层序遍历与队列

层序遍历按「先发现的先处理」展开,与队列的先进先出语义一致:节点出队时把其子节点入队,子节点的处理顺序自然等于发现顺序。这一「用队列实现广度优先」的对应关系见 栈与队列。树是图的特例,把「子节点」换成「全部邻居」并加上访问标记,即得到图的广度优先与深度优先遍历,见 图的表示与遍历。

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();       // 先固定本层节点数,循环中入队的都是下一层
        List<Integer> level = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

要点是 int size = queue.size() 必须在处理本层之前取定。若把循环条件写成「队列非空」,同一层的节点会与下一层的节点混合输出,这是层序类题目最常见的错误。

size 的取值同时给出了层内计数能力,由此可以直接计算树的宽度(各层节点数的最大值)与最小深度(第一个出现的叶子所在层)。

复杂度为 O(n) 时间;空间为 O(w),w 为树的最大层宽。这个上界与深度优先的 O(h) 是两个不同方向的界:满二叉树的宽度为 ⌈n/2⌉(最底层),因此层序遍历的空间是 O(n);而深优遍历在满二叉树上只需 O(log n)。选择哪种遍历顺序,除了访问次序的语义,也要考虑空间。

4. 由遍历序列还原

4.1 前序与中序还原

推导链条如下:

前序序列的第一个元素是整棵树的根
在中序序列中找到该根,其左侧是左子树的中序序列,右侧是右子树的中序序列
左子树的节点个数 = 中序中根的下标 − 中序区间起点
前序序列中,紧随根之后的 leftSize 个元素是左子树的前序序列,其余为右子树
对左右子树递归执行上述过程
HashMap<Integer, Integer> indexInOrder;      // 值 → 中序下标,预处理一次,避免每层线性查找

TreeNode build(int[] pre, int preLo, int preHi, int inLo, int inHi) {
    if (preLo > preHi) return null;          // 空区间对应空子树
    int rootVal = pre[preLo];
    int mid = indexInOrder.get(rootVal);
    int leftSize = mid - inLo;
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, preLo + 1, preLo + leftSize, inLo, mid - 1);
    root.right = build(pre, preLo + leftSize + 1, preHi, mid + 1, inHi);
    return root;
}

复杂度:预处理映射 O(n),递归体每层常数工作,共 n 个节点,时间 O(n);递归深度等于树高,空间 O(h)。

若不做映射预处理,每层在中序序列中线性查找根的位置,最坏情况(退化为链)总代价为 O(n²)。

4.2 中序与后序还原

原理对称:后序序列的最后一个元素是整棵树的根,在中序序列中划分左右子树后,后序序列的前 leftSize 个元素属于左子树,紧接的若干元素属于右子树,最后一个属于根。

后序 + 中序:
    左子树大小 = (中序中根的下标) − (中序区间起点)
    左子树后序区间 [postLo, postLo + leftSize − 1]
    右子树后序区间 [postLo + leftSize, postHi − 1]
    根在 postHi

4.3 为什么必须有中序

前序与后序都只能确定「根在哪里」,不能确定左右子树的分界。中序序列的作用正是提供这条分界线——根把中序序列切成两段,段长即子树规模。

只用前序 + 后序的失败例子:
    前序 [1, 2]      后序 [2, 1]
    根为 1,2 是 1 的左孩子还是右孩子?
    两种形态的前序与后序都与给定序列一致,无法区分

    前序 [1, 2, 3]   后序 [3, 2, 1]
    1 只有一个孩子(2),2 只有一个孩子(3)
    两支链的左右选择组合共有 2² = 4 种形态,均与给定序列一致

一般结论是:每个只有一个子节点的节点都会带来一次左右二义性,因此前序与后序无法唯一确定树形。只要序列中包含中序(或与之等价的、能给出左右规模划分的信息),还原结果才唯一。

由此得到三条判断规则:

给定序列 能否唯一还原 说明
前序 + 中序 能 前序定根,中序分界
中序 + 后序 能 后序定根,中序分界
前序 + 后序 不能 缺少分界信息,单子节点处二义
层序 + 中序 能 层序按层给出根,中序分界,还原过程用队列辅助
中序 + 仅为「BST」约束 能 BST 的中序递增,中序序列本身可作为分界依据

补充一点:若已知树是满二叉树(每个内部节点都有两个孩子),前序与后序可以唯一还原,因为不存在只有一个子节点的节点,二义性消失。

4.4 序列化与反序列化

把树转成可存储、可传输的线性表示称为序列化。可靠的做法必须满足「反序列化能唯一还原原树」这一要求,因此关键在于处理空节点。

// 前序序列化:用 # 记录空节点
void serialize(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,");
        return;
    }
    sb.append(node.val).append(',');
    serialize(node.left, sb);
    serialize(node.right, sb);
}

// 对应的反序列化:按前序消费,遇到 # 返回空
int cursor = 0;
TreeNode deserialize(String[] tokens) {
    String token = tokens[cursor++];
    if ("#".equals(token)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(token));
    node.left  = deserialize(tokens);
    node.right = deserialize(tokens);
    return node;
}

几种常见表示的取舍:

表示 是否唯一还原 特点
前序 + 空节点标记 是 实现最简单,冗余度为每个空引用一个标记,总长度约 2n
中序 + 后序 是 无冗余标记,但需要两个序列
括号表示(1(2,3)) 是 可读性好,适合调试输出
层序 + 空节点标记 是 适合需要逐层读写的场景,尾部空节点可省略
仅中序 否 无法确定层次结构
仅前序或仅后序 否 单子节点处二义

注意反序列化时消费空节点标记的必要性:若序列化时省略空节点标记,还原过程将无法判断某个节点是否有左孩子,形状稍有差异的树会得到相同的序列,这是序列化实现中最典型的功能性缺陷。

5. 二叉搜索树

5.1 有序性与中序遍历

二叉搜索树(Binary Search Tree,BST)在二叉树的结构之上附加一条约束:

对任意节点 x:
    x 左子树中所有节点的值 < x 的值
    x 右子树中所有节点的值 > x 的值

这条约束作用于整个子树,而不是只作用于直接子节点,这是与「只比较父子」的常见误解的分界。它带来的核心性质是:

对二叉搜索树进行中序遍历,得到的序列严格递增

推理是:中序遍历的次序为「左子树全部节点 → 根 → 右子树全部节点」,而约束保证左子树全部小于根、右子树全部大于根,递归展开即得整条序列有序。

两点需要补充:

  • 是否允许重复值由约定决定。允许重复时通常规定「小于等于放左子树」或「大于等于放右子树」,并使用其中一侧的严格不等号维持一致性。约定一旦选定,查找、插入、删除都必须遵循同一规则,否则会出现「插入成功但找不到」的故障。
  • 中序有序是 BST 与堆的分界。堆只要求父子之间有序,兄弟之间没有约束,因此堆的中序遍历无序,而堆能在 O(1) 取到最值。BST 要求在全部节点上全局有序,因此可以在 O(log n) 内完成查找、前驱后继、范围查询,但取最值也只需 O(log n)。两者的取舍见第三节 5.3 节。

5.2 查找

从根开始:
    目标等于当前节点的值 → 命中,返回
    目标小于当前节点的值 → 进入左子树
    目标大于当前节点的值 → 进入右子树
    走到空节点 → 不存在

每一步排除一整棵子树,因此代价等于查找路径的长度,即从根到目标节点的层数。树高为 h 时,一次查找最多比较 h 次,最坏情况与平均情况的差别全部来自树形(见第 6 节)。

迭代写法比递归写法更常用:查找不需要回溯,循环即可完成,且不受递归深度限制。

TreeNode search(TreeNode root, int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (key == cur.val) return cur;
        cur = (key < cur.val) ? cur.left : cur.right;
    }
    return null;
}

5.3 插入

插入位置由查找过程唯一确定:沿着查找路径前进,走到空引用处即为新节点的位置。因此插入的代价与查找相同,均为 O(h)。

新插入的节点一定是叶子。这一性质来自约束本身:若新节点的位置在内部,说明该位置原本存放着一个满足约束的节点,路径上就不会出现空引用。这也是「插入不需要调整已有节点的位置」的原因——BST 的插入只增加节点,不做旋转,结构的平衡性完全依赖插入顺序。

插入的实现需要一个常被忽略的细节:必须把新节点挂到父节点上。递归写法通过返回值完成挂接,迭代写法需要记录父节点。

// 递归写法:返回值为「本子树处理后的根」,由调用方挂接
TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);     // 到达空位置,生成新节点
    if (key < root.val) {
        root.left = insert(root.left, key);         // 挂接可能发生变化的左子树根
    } else if (key > root.val) {
        root.right = insert(root.right, key);
    }
    // key == root.val:已存在,按「不重复」约定不做处理
    return root;
}

若去掉 root.left = ... 的赋值而直接调用 insert(root.left, key),新节点会被创建但不会被任何节点引用到,插入静默失效——查找时返回不存在,而树的结构看起来毫无异常。这是 BST 实现中最常见的缺陷之一。

5.4 删除

删除是三种操作中唯一需要分类讨论的,按被删节点的度分三种情形。

情形一:被删节点是叶子(度为 0)
    直接删除,把父节点对应的子引用置空

情形二:被删节点只有一个子树(度为 1)
    用其唯一的子树替代它的位置,即把父节点的对应子引用指向该子树的根
    (整个子树搬移,不需要逐个节点处理)

情形三:被删节点有两个子树(度为 2)
    需要保持中序有序性,做法是:
      1. 找到中序后继(右子树中最左的节点)或中序前驱(左子树中最右的节点)
      2. 用后继(或前驱)的值覆盖被删节点的值
      3. 问题转化为「删除后继节点」,而后继节点没有左子树,属于情形一或情形二
TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = delete(root.left, key);
    } else if (key > root.val) {
        root.right = delete(root.right, key);
    } else {
        if (root.left == null)  return root.right;   // 情形一与情形二合并:无左子树时用右子树顶替
        if (root.right == null) return root.left;    // 情形二:只有左子树
        TreeNode succ = root.right;                  // 情形三:取中序后继
        while (succ.left != null) succ = succ.left;
        root.val = succ.val;                         // 值替换
        root.right = delete(root.right, succ.val);   // 在后子树中删除后继节点
    }
    return root;
}

几处容易出错的点:

  • 情形一与情形二在代码中合并。root.left == null 时返回 root.right:若右子树也为空,返回的 null 恰好完成叶子删除;若右子树存在,则完成单子树顶替。这一合并简化了分支,也是理解这段代码的关键。
  • 情形三先替换值再删后继,而不是调整指针。另一种实现是把后继节点整体「摘下来」接到被删位置,同时正确接续后继的右子树与父引用,指针操作更多,出错面更大。
  • 必须接续子树,而不是丢弃。删除度为 1 的节点时只把该节点置空,会连同它唯一的子树一起丢失,这类缺陷在结构上表现为「元素数量少于预期」。
  • 返回值必须被挂接。与插入相同,root.left = delete(root.left, key) 的赋值不能省略。
  • 删除最后剩下一个节点时返回 null,调用方必须把返回值赋给根引用,因此删除接口通常设计为返回新的根(或使用哨兵根节点使根引用永不变化)。

删除的时间复杂度同样是 O(h):查找目标节点 O(h),在度为 2 的情形下再找一次后继 O(h)。删除内部节点会导致树形变化,且两种后继选择策略对树形的影响不同:始终取右子树最左节点会使左侧偏高,交替使用前驱与后继可以缓解倾斜,但都不能从根本上保证平衡。

5.5 前驱与后继

中序前驱是在中序序列中排在给定节点之前的节点,中序后继是排在其后的节点。

后继的求法:
    若节点有右子树 → 后继是右子树中最左的节点(一路向左到底)
    若节点没有右子树 → 后继是「最近的、该节点位于其左子树中的祖先」
                     即沿父指针向上,直到当前节点是父节点的左孩子,该父节点即后继

前驱的求法对称:
    若有左子树 → 左子树中最右的节点
    若无左子树 → 沿父指针向上,直到当前节点是父节点的右孩子

没有父指针时,第二种情形需要从根开始重新查找,代价 O(h);有父指针时可以沿链上行,整体均摊 O(1)。这解释了 2.1 节中「是否需要父指针」这一取舍:TreeMap 的迭代器需要高效的双向移动,因此其节点保存了父指针。

前驱与后继在删除操作(情形三)、范围查询的边界处理、有序迭代器中都要用到,是 BST 的基本操作之一。

5.6 范围查询与最值

最值:最小值是一路向左走到底的节点,最大值是一路向右走到底的节点,代价 O(h)。这与堆的 O(1) 取最值形成对照——堆的堆顶即最值,但代价是失去全局有序。

范围查询(返回 [low, high] 内的全部元素)有本质区别:结果规模可以达到 O(k),而 k 可能远大于 log n,因此任何范围查询的下界是 O(k)。在 BST 上可以做到 O(h + k),即只访问「必要的路径 + 结果本身」。

void rangeQuery(TreeNode node, int low, int high, List<Integer> res) {
    if (node == null) return;
    if (node.val > low) {
        rangeQuery(node.left, low, high, res);       // 左子树可能有命中,需要进入
    }
    if (node.val >= low && node.val <= high) {
        res.add(node.val);
    }
    if (node.val < high) {
        rangeQuery(node.right, low, high, res);      // 右子树可能有命中,需要进入
    }
}

剪枝依据:当前节点的值不大于 low 时,左子树全部更小,必然没有命中,直接跳过;值不小于 high 时跳过右子树。只做遍历不加剪枝的写法代价为 O(n),在范围很窄的情况下浪费巨大。

另一种实现思路是先沿树定位到 low 的位置,再从中序后继逐跳前进,直到超过 high。两种做法都不改变 O(h + k) 的量级,但后者在结果稀疏时更省常数。

6. 退化问题

6.1 有序插入导致退化为链表

BST 的结构完全由插入顺序决定,而插入只增加叶子节点,不做任何形状调整。因此

按升序插入 1, 2, 3, 4, 5:

    1
     \
      2
       \
        3
         \
          4
           \
            5

每个节点都只有右子节点,树高 = 节点数 = 5

这正是 BST 最脆弱的场景,而且它不是罕见输入:按主键顺序插入数据、按时间顺序导入记录、从已排序文件中读取数据,都会自然地产生有序插入。排序本身是最常见的预处理,却恰好是 BST 最坏的输入形状。

TreeNode root = null;
for (int i = 1; i <= n; i++) {
    root = insert(root, i);      // 每次都在最右侧扩展,树高线性增长
}

6.2 复杂度从 O(log n) 变为 O(n)

操作 平衡形态(h = O(log n)) 退化形态(h = n)
查找 O(log n) O(n)
插入 O(log n) O(n)
删除 O(log n) O(n)
求最值 O(log n) O(n)
中序遍历 O(n) O(n)
递归遍历的栈空间 O(log n) O(n)
层序遍历的队列空间 O(w) O(1)

表中最后三行说明一件容易被忽略的事:中序遍历的代价与树形无关(每个节点都访问一次),但递归实现的栈空间与层序遍历的峰值宽度都与树形直接相关。退化为链时,递归的深度达到 n,可能直接触发栈溢出。

以 n = 10⁶ 为例:平衡形态下查找约 20 次比较,退化形态下约 10⁶ 次比较,相差五个数量级。同一个数据结构、同一份代码,只因输入顺序不同,性能就从可用变为不可用——这是 BST 与哈希表、数组等其他结构在工程风险上的根本差异:它的复杂度不是一个由类型决定的承诺,而是依赖于运行时数据分布的偶然性质。

更隐蔽的一点是退化后的排查难度:代码没有任何异常,接口行为完全正确,只是变慢;而变慢的根因在数据结构的使用方式中,而不是在某次调用的实现里。因此对 BST 而言,「是否可能有序插入」是一个必须在设计阶段回答的问题。

6.3 平衡的必要性与解决方向

平衡的目的只有一个:把树高从最坏 O(n) 拉回到 O(log n),使复杂度成为结构本身提供的保证,而不是输入顺序带来的运气。围绕这一点有四条技术路线。

路线一:在节点上维护平衡信息,通过旋转恢复。 这是自平衡二叉搜索树的共同做法,代表是 AVL 树与红黑树,两者的平衡条件、旋转与删除调整见 平衡树:AVL 与红黑树。AVL 树严格限制左右子树高度差不超过 1,因此查找路径最短,但插入删除的旋转调整更频繁;红黑树放宽到「最长路径不超过最短路径的两倍」,查找略慢,插入删除的调整次数有常数上界。红黑树因此成为多数标准库有序映射的实现选择,其五条性质、旋转与重新着色机制见 Java 集合框架实现原理 中 TreeMap 的部分。

路线二:放弃严格平衡,采用随机化。 随机化 BST(treap)为每个节点附加随机优先级,在保持 BST 的键序的同时按优先级维护堆序,从而在概率意义下得到 O(log n) 的期望高度;跳表用多层索引达到同一效果,实现上比旋转更简单,且更容易支持并发。跳表的原理与它在链表上的派生关系见 跳表。

路线三:在插入顺序上做约束。 把有序输入打乱、或先构建平衡形态再插入,可以避免退化,但这属于使用方约定,不是结构提供的保证,适合初始化一次、之后只读的场景。

路线四:改用多路结构。 当节点数量巨大且存储以块为单位访问时,二叉树的分支因子太小,树高成为瓶颈。多路平衡树(B 树、B+ 树,定义与页组织见 B 树与 B+ 树)把每个节点的键数量提高到数百,使树高降到 3 至 4 层,从而把「磁盘 IO 次数」压到很小的常数。数据库索引的选择与页大小对树高的影响见 mysql: 索引与执行计划。

这四条路线的共同点是:用额外的结构信息或访问顺序上的约束,换取树高的上界保证。代价是每节点更多的字段、每次修改更多的调整动作,或读取方式的限制。是否需要付出这些代价,由「能否接受最坏情况下退化为线性」这一判断决定。

7. 树与递归

7.1 递归三要素在树上的体现

编写一个正确的递归函数,需要明确三件事,树的问题恰好把这三件事各自对应到一个具体的判断点。

要素 含义 在树上的对应
终止条件 何时不再递归,直接返回 node == null 时返回什么;叶子节点是否需要单独处理
单层逻辑 本层做什么,与子树的关系 处理根、递归左右子树的先后次序
返回值含义 每层向外传递什么 返回值是「子树的高度」「子树是否平衡」「子树内的答案」,还是「新的子树根」

其中返回值含义最容易被忽略。树问题的递归函数往往需要同时处理两类信息:只与子树相关的结果(子树高度)与跨越根的结果(经过根的最长路径)。若返回值只能携带一种,另一种就必须通过外部变量或引用参数携带。直径问题(见第三节 4.7 节)是典型例子:函数返回高度,而在每层用左右高度之和更新外部记录的最大直径。

终止条件的处理同样有陷阱。「空节点返回什么」决定了整棵树为空的边界行为:求高度时空节点返回 0;求节点数时返回 0;求路径和时空节点返回「不存在路径」而非 0,因为 0 在目标值为 0 时会产生假阳性。这条边界必须在写递归之前确定,否则会在后续调试中反复修改。

7.2 自顶向下与自底向上

树的递归有两种形态,区别在于信息流动方向。

自顶向下(top-down):把「从根到当前节点的上下文」作为参数传入,每个节点利用上下文做出判断并向下传递。不需要返回值参与求解,返回值只用于控制流程。

适合的问题特征是:判断依赖祖先信息。例如校验 BST 需要携带上下界(当前节点必须落在 (low, high) 开区间内,进入左子树时上界收缩为当前值,进入右子树时下界收缩为当前值);求所有从根到叶的路径需要携带「已走过的路径」;求路径和需要携带「剩余目标值」。

// 自顶向下:把有效区间作为参数向下传递
boolean isValidBST(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return isValidBST(node.left, low, node.val)
        && isValidBST(node.right, node.val, high);
}

自底向上(bottom-up):先递归求子树的解,再在本层把子树的解合并。返回值承载子问题的答案。

适合的问题特征是:答案可以由子树答案组合。例如求高度(左右高度的最大值加 1)、求节点数(左右之和加 1)、判断平衡(由左右高度差判断,并把高度向上返回)、求直径(左右高度之和与本层最大值)、求最近公共祖先(左右子树是否各自找到目标)。

// 自底向上:返回值是子树高度,本层负责合并
int height(TreeNode node) {
    if (node == null) return 0;
    return Math.max(height(node.left), height(node.right)) + 1;
}
形态 信息方向 返回值作用 典型问题
自顶向下 根 → 叶 控制流程(是否需要继续递归) BST 校验、路径和、根到叶路径枚举、深度限制搜索
自底向上 叶 → 根 承载子问题答案 高度、节点数、平衡判定、直径、最近公共祖先

自底向上的一个重要优势是可以一次遍历同时算出多个量,从而避免重复遍历。判断平衡时若分开写「求高度」与「比较高度」,每个节点都要重复计算子树高度,最坏复杂度退化为 O(n²);而自底向上只遍历一次,遇到不平衡立即剪枝返回,复杂度 O(n)。这类「用返回值合并多项信息、一次遍历完成」的技巧是树算法的核心优化手段。

7.3 回溯与剪枝

回溯在树上表现为「进入子树前修改共享状态,返回后恢复」。求所有根到叶路径的算法中,路径列表在多条分支之间共享,因此

void dfs(TreeNode node, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    path.add(node.val);                       // 进入:加入当前节点
    if (node.left == null && node.right == null) {
        res.add(new ArrayList<>(path));       // 叶子:复制一份结果,不能直接存引用
    }
    dfs(node.left, path, res);
    dfs(node.right, path, res);
    path.remove(path.size() - 1);             // 返回:撤销本次选择
}

两处易错点:结果必须复制当前路径再保存,直接把 path 的引用放进结果集合会导致所有结果指向同一个列表;撤销动作必须放在两次递归之后,且必须与加入动作严格配对。

剪枝在树上表现为「根据已知条件提前放弃整棵子树」。三类常见剪枝:

  • 有序性剪枝。BST 上的范围查询中,节点值不小于上界时整棵右子树都不可能命中,直接返回,使代价从 O(n) 降到 O(h + k)。
  • 上下界剪枝。带深度限制的搜索(迭代加深、深度受限的 DFS)在超出剩余深度时立即返回,避免探索不可能包含解的子树。
  • 可行性剪枝。求路径和时,若已经超出目标值且节点值全为正数,可以直接返回,不需要继续深入。

剪枝的判断依据必须来自问题的约束(有序性、单调性、上下界),而不是「看起来不太可能」。缺乏依据的剪枝会漏解,这类错误比不剪枝更难发现,因为结果只在特定输入下出错。

三、实现

1. 节点结构与遍历实现

1.1 节点定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

需要携带父指针或子树统计信息时按需扩展(见第二节 2.1 节的取舍讨论);不需要的字段不预先添加,因为每个新增字段都必须在所有结构修改处同步维护。

1.2 递归遍历

void traverse(TreeNode node, List<Integer> res, Order order) {
    if (node == null) return;
    if (order == Order.PRE)  res.add(node.val);   // 前序:根在最前
    traverse(node.left, res, order);
    if (order == Order.IN)   res.add(node.val);   // 中序:根在中间
    traverse(node.right, res, order);
    if (order == Order.POST) res.add(node.val);   // 后序:根在最后
}

把三种次序写在一个函数中只用于说明区别,实际代码应拆成三个函数:合并写法在每个节点增加了两次判断,且让「根的访问时机」这一关键信息分散在条件分支中。

递归实现的运行前提是递归深度等于树高。树高可能达到 n 时(如未做平衡的 BST),递归版本存在栈溢出风险,此时应改用显式栈。

1.3 非递归遍历

三种次序的迭代实现需要区分两类结构:用栈模拟递归(前序、中序、后序)与用队列按层展开(层序)。前序与中序的写法见第二节 3.3 节,后序用「根右左入栈、结果头插」的双栈思路实现。

List<Integer> postorder(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        res.addFirst(node.val);
        if (node.left != null)  stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return res;
}

验证正确性的方法是核对出栈次序:由于先压左后压右,出栈顺序为「根、右、左」,而 addFirst 使结果与出栈顺序相反,因此为「左、右、根」,即后序。这类「通过入栈顺序与输出位置配合」的写法需要显式验证一次,不宜凭直觉记忆。

1.4 层序遍历

层序实现的关键是在进入本层循环之前固定本层节点数,代码见第二节 3.5 节。需要按层聚合以外的场景(例如只求宽度、只求最小深度)可以在同一骨架上删减:宽度取各层 size 的最大值,最小深度在首次遇到叶子时返回当前层号。

1.5 遍历结果的应用

遍历结果本身也是一份结构化数据,常见应用有三类。

序列化与存储。前序加空节点标记是唯一还原的最简方案(见第二节 4.4 节)。选择前序而不是中序的原因是前序的根位置固定在最前,反序列化可以顺序消费而无需回溯。

合法性校验。BST 的中序遍历必须严格递增,因此「中序遍历 + 严格递增判断」是校验 BST 最直观的方法;它不依赖递归传递上下界,代码更短,代价是需要 O(n) 的额外数组(或在遍历过程中只保存前一个值,把空间降到 O(1))。

结构比较。判断两棵树是否完全相同,用前序或后序同步遍历比较结构与值即可;判断一棵树是否是另一棵的子树,通常先做序列化再用字符串匹配,或直接同步遍历比较。

2. 二叉搜索树实现

2.1 查找与插入

class BST {
    private TreeNode root;

    TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (key == cur.val) return cur;
            cur = (key < cur.val) ? cur.left : cur.right;
        }
        return null;
    }

    void insert(int key) {
        if (root == null) {
            root = new TreeNode(key);         // 空树:新节点成为根
            return;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            parent = cur;
            if (key == cur.val) return;       // 已存在,按不重复语义直接返回
            cur = (key < cur.val) ? cur.left : cur.right;
        }
        if (key < parent.val) {
            parent.left = new TreeNode(key);
        } else {
            parent.right = new TreeNode(key);
        }
    }
}

迭代插入的要点是保存 parent:循环结束时 cur 为 null,只有父节点仍在作用域内,遗漏 parent 会导致新节点无法挂接。递归版本通过返回值挂接(见第二节 5.3 节),逻辑更短但受递归深度限制。

2.2 删除

删除的三种情形与递归实现见第二节 5.4 节。需要额外强调两点工程细节。

根引用的更新。删除根节点(尤其是根为叶子或只有一棵子树)会改变根引用,因此删除接口必须返回新的根,并由调用方重新赋值;另一种做法是使用哨兵根节点,让 root 引用永不变化,代价是多一个节点与一层间接。

父指针场景的额外维护。若节点保存了父指针,删除度为 1 的节点时需要同时把子树的 parent 指向被删节点的父节点;情形三中删除后继节点后也要修正其右子树的父指针。遗漏这两处不会立即报错,但会使后续「从节点向根回溯」的操作走到错误的位置。

2.3 范围查询与前驱后继

范围查询的实现与剪枝依据见第二节 5.6 节。前驱与后继的两种情形见第二节 5.5 节,无父指针时的向上查找需要从根重新定位,可写成「在查找 key 的过程中记录最后一个小于 key 的节点」,一趟完成。

// 无父指针:一趟查找同时给出小于 key 的最大值(前驱)
Integer floor(int key) {
    Integer best = null;
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == key) return key;
        if (cur.val < key) {
            best = cur.val;                   // 候选前驱,继续向右找更大的
            cur = cur.right;
        } else {
            cur = cur.left;
        }
    }
    return best;
}

2.4 合法性校验

常见错误写法:只比较节点与直接子节点的大小关系。

// 错误:只检查直接子节点
boolean badIsValid(TreeNode node) {
    if (node == null) return true;
    if (node.left != null && node.left.val >= node.val) return false;
    if (node.right != null && node.right.val <= node.val) return false;
    return badIsValid(node.left) && badIsValid(node.right);
}
反例:
            10
           /  \
          5    15
              /
             6

每个节点与直接子节点的比较都满足约束:15 > 10,6 < 15
但 6 位于 10 的右子树中,6 < 10,违反 BST 的整体约束
上述写法会错误地判定这棵树合法

根因是 BST 的约束作用于整棵子树,而局部比较只能校验一条边。正确的两种写法:

// 写法一:自顶向下传递开区间 (low, high)
boolean isValidBST(TreeNode node, Long low, Long high) {
    if (node == null) return true;
    if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
        return false;
    }
    return isValidBST(node.left, low, (long) node.val)
        && isValidBST(node.right, (long) node.val, high);
}
// 调用:isValidBST(root, null, null)
// 写法二:中序遍历必须严格递增
Long prev = null;

boolean isValidBST(TreeNode node) {
    if (node == null) return true;
    if (!isValidBST(node.left)) return false;
    if (prev != null && node.val <= prev) return false;    // 严格递增,等号也不能出现
    prev = (long) node.val;
    return isValidBST(node.right);
}

边界值处理。若上下界使用基本类型 int,节点值恰好等于 Integer.MIN_VALUE 或 MAX_VALUE 时会出现「边界与不存在的界无法区分」的问题:以 Integer.MIN_VALUE 表示「无下界」时,值等于该数的节点会被误判。解决办法是使用 long 并把初始界设为 Long.MIN_VALUE / Long.MAX_VALUE,或用可空的包装类型,或改用中序比较法。这类边界缺陷只在极值输入下出现,测试用例必须显式覆盖。

3. 复杂度分析

3.1 平均与最坏情况对比

操作 平衡 BST(h = O(log n)) 随机形态 BST(期望) 退化 BST(h = n)
查找 O(log n) O(log n) O(n)
插入 O(log n) O(log n) O(n)
删除 O(log n) O(log n) O(n)
最小值 / 最大值 O(log n) O(log n) O(n)
前驱 / 后继(有父指针) 均摊 O(1) 均摊 O(1) 均摊 O(1)
前驱 / 后继(无父指针) O(log n) O(log n) O(n)
范围查询 [low, high] O(log n + k) O(log n + k) O(n)
中序遍历 O(n) O(n) O(n)
空间(节点数) O(n) O(n) O(n)
递归栈空间 O(log n) O(log n) O(n)

所有基于树高的操作都由树高决定,因此可以写成统一口径:查找、插入、删除均为 O(h)。这一写法比记忆「O(log n)」更准确,因为它把平衡性这一前提显式写了出来。对照哈希表的期望 O(1) 与最坏 O(n)、数组的 O(1) 定位,可以看清三类结构的定位依据不同:数组按地址算术,哈希表按散列函数,BST 按比较路径。哈希表不提供有序性与范围查询,其代价与均摊结论见 哈希表。

3.2 随机插入的期望高度

插入顺序随机时,BST 的形状不再是任意的,其高度有明确的期望上界。

随机插入构造的 BST(每个输入次序等概率):

    平均查找代价(节点平均深度)  → 约 2 ln n ≈ 1.386 log₂n
    树高的期望                    → 约 4.311 ln n ≈ 2.99 log₂n
    结论:树高与查找代价均为 O(log n) 的常数倍

两项结果的量级相同,但常数不同:平均节点的深度远小于最坏节点(最深叶子)的深度,这正是「平均情况」与「最坏情况」在树上的具体差别。随机 BST 的高度集中在期望值附近,偏离超过常数倍的输入占比随 n 增大而快速下降。

n = 10³      平衡形态高度约 10     随机 BST 期望高度约 30
n = 10⁶      平衡形态高度约 20     随机 BST 期望高度约 60
n = 10⁹      平衡形态高度约 30     随机 BST 期望高度约 90

这张表同时给出了随机化的收益与代价:与理想平衡相比,随机 BST 的高度大约是 3 倍,常数上的损失约为 3 倍比较次数——这通常可以接受;而与有序插入造成的 O(n) 相比,节省的量级是数量级的差别。因此在实际工程中,即使不要求严格的 O(log n) 保证,避免有序插入也应当作为硬性约束。

复杂度记号的使用边界(大 O 描述上界而非最坏情况的同义词、平均结论必须与分布假设一同给出、常数因子与缓存行为对实测的影响)见 复杂度与算法分析。

4. 常见算法问题

4.1 最大深度

自底向上:空节点高度为 0,非空节点高度为左右子树高度的较大值加 1。时间 O(n)(每个节点访问一次),空间 O(h)(递归栈)。

int maxDepth(TreeNode node) {
    if (node == null) return 0;
    return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
}

最小深度不能用同样的对称写法:最小深度定义为「从根到最近的叶子节点的层数」,而空节点返回 0 会把「只有一侧子树」的节点误判为深度 1。正确写法需要区分「某侧子树为空」的情形,或改用层序遍历,在首次遇到叶子时返回当前层号。

4.2 平衡判定

自底向上一次遍历完成:返回值是子树高度,若某棵子树已判定不平衡则返回 -1 并向上短路传递,父节点不再计算。时间 O(n),空间 O(h)。

int check(TreeNode node) {           // 返回高度,或 -1 表示不平衡
    if (node == null) return 0;
    int left = check(node.left);
    if (left == -1) return -1;       // 剪枝:左子树已不平衡,无需再算右子树
    int right = check(node.right);
    if (right == -1) return -1;
    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
}

若改为「先递归判断左右子树是否平衡,再调用求高度函数比较高度差」,每个节点都会重复计算子树高度,最坏复杂度为 O(n log n)(平衡树上)甚至 O(n²)(退化树上)。用返回值同时承载「答案」与「供上层使用的中间量」是避免重复遍历的关键。

4.3 最近公共祖先

后序遍历:递归返回「该子树中是否找到了目标节点或找到了公共祖先」。

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;    // 两侧各找到一个,当前节点即答案
    return (left != null) ? left : right;              // 否则把已找到的一侧向上传递
}

时间 O(n),空间 O(h)。判断依据:两个目标节点分别在当前节点的两侧子树中时,最近公共祖先是当前节点;若两个目标都在同一侧,答案在该子树内。

在 BST 上可以利用有序性把代价降到 O(h):从根开始,若两个目标值都小于当前值则走向左子树,都大于则走向右子树,否则当前节点即答案(包括当前值等于其中一个目标的情况)。

4.4 路径和

求「是否存在一条根到叶的路径,其节点值之和等于目标」用自顶向下,参数携带剩余目标值。

boolean hasPathSum(TreeNode node, int target) {
    if (node == null) return false;
    if (node.left == null && node.right == null) {
        return node.val == target;              // 必须是叶子才构成合法路径
    }
    return hasPathSum(node.left, target - node.val)
        || hasPathSum(node.right, target - node.val);
}

求「所有满足条件的路径」时用回溯维护路径列表,进入节点时加入、离开时撤销,保存结果时复制当前路径(见第二节 7.3 节)。时间 O(n)(每个节点访问一次),空间 O(h) 加上结果本身的规模。

易错点是把终止条件写成 node == null 时判断 target == 0:会接受「中途某条路径的和恰好等于目标」而非「到叶子的完整路径」。

4.5 对称与镜像

判断一棵树是否左右对称,等价于判断根的两个子树是否互为镜像。镜像关系的比较需要交叉递归:一个节点的左子树与另一个节点的右子树配对比较。

boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}

boolean mirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && mirror(a.left, b.right)
        && mirror(a.right, b.left);
}

时间 O(n),空间 O(h)。关键点是两次递归的参数顺序相反,写成同侧比较(mirror(a.left, b.left))会变成「判断两棵树是否相同」。

4.6 层序按层输出

用队列 + 层大小(见第二节 3.5 节)。时间 O(n),空间 O(w),w 为最大层宽。变体包括锯齿形层序(偶数层反转)、自底向上层序(结果反转)、每层求平均值(层内累加后除以层大小)。

4.7 有序数组转为平衡 BST

取中点作为根,递归构造左右子树,保证左右节点数相差不超过 1,因此高度为 ⌊log₂n⌋ + 1,达到最小值。

TreeNode sortedArrayToBST(int[] nums, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;          // 防溢出的中点写法
    TreeNode root = new TreeNode(nums[mid]);
    root.left  = sortedArrayToBST(nums, lo, mid - 1);
    root.right = sortedArrayToBST(nums, mid + 1, hi);
    return root;
}

时间 O(n)(每个元素恰好成为一次根),空间 O(log n)(递归栈)。中点的取法决定了两侧节点数的分配:lo + (hi - lo) / 2 向下取整,左子树节点数不超过右子树,高度差不超过 1。

这一方法也说明了「有序输入」的正确用法:有序输入本身不构成问题,把它按中点分治构造成平衡形态,正好利用了有序性,与「逐个插入有序元素」的破坏性用法形成对照。

4.8 节点计数与直径

节点计数:空节点返回 0,非空返回左右之和加 1,O(n)。

直径(任意两节点间最长路径的边数)需要同时用到「子树高度」与「跨根的路径长度」两类信息:函数返回高度,在每层用左右高度之和更新外部记录的最大值。

int diameter = 0;

int depth(TreeNode node) {
    if (node == null) return 0;
    int left = depth(node.left);
    int right = depth(node.right);
    diameter = Math.max(diameter, left + right);      // 经过当前节点的最长路径
    return Math.max(left, right) + 1;                 // 向上返回的是高度
}

时间 O(n),空间 O(h)。注意最长路径不一定经过根,因此不能只在根处计算左右高度之和,必须在每个节点处都更新一次。

4.9 汇总

问题 主要方法 时间 额外空间 易错点
最大深度 后序递归 O(n) O(h) 最小深度不能套用同样写法
平衡判定 后序递归 + 短路剪枝 O(n) O(h) 分开求高度会重复遍历
最近公共祖先 后序递归 O(n)(BST 上 O(h)) O(h) 返回值语义需先确定
路径和 自顶向下携带剩余值 O(n) O(h) 必须判叶子,不能判空节点
对称判定 交叉递归 O(n) O(h) 两次递归参数顺序相反
层序按层输出 队列 + 层大小 O(n) O(w) 层大小必须在循环前取定
有序数组转平衡树 分治取中点 O(n) O(log n) 中点写法与取整方向
直径 后序递归 + 外部变量 O(n) O(h) 需在每个节点更新,不能只在根
节点计数 后序递归 O(n) O(h) 空节点返回值与叶子返回值需区分
校验 BST 中序递增 / 上下界传递 O(n) O(h) 或 O(1) 只比较直接子节点会误判

5. 工程应用

5.1 表达式树与语法树

算术表达式可以表示为二叉树:叶子是操作数,内部节点是运算符,左右子树分别是被操作的两个子表达式。这种表示把「运算次序」编码进树形,从而不需要括号。

中缀表达式 (a + b) * (c − d) 的表达式树:

            *
          /   \
         +     −
        / \   / \
       a   b c   d

三种遍历对应三种表达式记法:
    前序遍历 → * + a b − c d     前缀表达式(波兰式),无需括号
    中序遍历 → a + b * c − d     中缀表达式,需要按优先级补括号
    后序遍历 → a b + c d − *     后缀表达式(逆波兰式),无需括号,可直接用栈求值

由此得到表达式求值的两种实现路径:先把中缀表达式转成后缀表达式再用栈求值(转换与求值机制见 栈与队列),或直接构造表达式树后做后序遍历。后者的优势在于可以对树做变换——常量折叠、公共子表达式消除、代数化简——都对应到局部的树改写。

语法树(AST) 是表达式树的推广:内部节点可以有多个子节点(一个语句包含多个子表达式),节点类型对应语法产生式。编译器前端输出 AST、语义分析在 AST 上标注类型、代码生成自 AST 后序遍历生成指令序列,这一流程的结构与表达式树完全同构。语法分析中的递归下降、算符优先等方法的实现基础也是树形的语法结构。

5.2 决策树与分类

决策树把「根据若干特征做出判断」的过程表示为一棵树:内部节点是一个特征的判断,分支是该判断的取值,叶子是最终结论(分类标签或预测值)。从根到叶的一条路径对应一条完整的判断规则,因此单条规则的可解释性是该模型最突出的性质。

构造过程是自顶向下的递归划分:在当前节点上选择某个特征与切分点,把样本集划分到子节点,对每个子节点递归执行,直到满足停止条件(节点内样本同属一类、样本数低于阈值、树深达到上限)。不同算法的区别在于划分准则:

算法 划分准则 特点
ID3 信息增益 偏向取值数目多的特征
C4.5 信息增益率 对取值数目做归一化,缓解上述偏向
CART 基尼指数 只产生二叉划分,便于处理连续特征与回归任务

决策树在树形结构上的问题与 BST 有对应关系:树太深会过拟合(训练集上错误率低、测试集上高),对应 BST 的形态失衡问题;解决办法是剪枝——预剪枝在构造时提前停止分裂,后剪枝在构造完成后自底向上用验证集判断是否把子树折叠为叶子,对应 BST 的平衡调整。单棵决策树的方差较大,集成方法(随机森林、梯度提升树)用多棵树的组合降低方差,代价是失去单棵树的可解释性。

5.3 堆与优先队列

堆是一棵完全二叉树,并满足堆序性质:每个节点的值不大于(小顶堆)或不小于(大顶堆)其子节点的值。它与 BST 的关系可以用一句话区分:

结构 有序性范围 取最值 查找任意值 存储
二叉搜索树 全局有序(中序递增) O(log n) O(log n) 链式(也可用数组)
二叉堆 只有父子有序,兄弟无序 O(1) O(n) 数组(利用完全二叉树编号)

堆放弃了「查找任意元素」的能力,换来 O(1) 取最值与原地存储。它的数组存储正是第二节 2.2 节讨论的完全二叉树下标关系:无引用字段、父子访问由算术给出、不需要队列即可按层处理。建堆、上浮与下沉、堆排序以及与快速选择的对比见 堆与优先队列;优先队列的队列语义、延迟任务与时间轮的取舍见 栈与队列 的优先队列一节。

5.4 数据库与文件系统索引

内存中的 BST 与磁盘索引的关键差异是访问成本的单位。内存访问的代价与访问位置无关(命中缓存时更是如此),而磁盘访问以块(页)为单位,一次页读取的代价是内存访问的数个数量级。B+ 树的树高被压到 3 至 4 层,定位一行只需 1 至 2 次物理读,页大小、扇出与树高的推导见 mysql: 索引与执行计划。

若把二叉搜索树直接放在磁盘上,情况会完全不同:每个节点只保存一个键与两个指针,一次比较就要读一个页,而树高为 O(log n)。以 10⁶ 行数据估算,二叉树需要约 20 次页读取,B+ 树只需 3 至 4 次。差距来自分支因子:

二叉树:每个节点 2 个分支   → 树高 ≈ log₂n
B+ 树:每个页节点约 1000 个分支(16KB 页 / 约 16B 每项)→ 树高 ≈ log₁₀₀₀ n

n = 10⁶:二叉树约 20 层,B+ 树约 2 层
n = 10⁹:二叉树约 30 层,B+ 树约 3 层

除分支因子外,B+ 树还做了一项针对磁盘的调整:所有数据都放在同一层的叶节点上,叶节点之间用双向链表连接。前一节提到的「有序数组转为平衡 BST」解决了树高问题,但范围查询仍需要中序遍历、跳跃访问分散的节点;叶层链表使范围扫描退化为顺序读,把随机读变为顺序读。

同一思路也出现在文件系统中:目录项的组织、某些文件系统的元数据索引(如 B 树文件系统)同样采用多路平衡结构,理由是相同的——减少需要读取的块数。这也是「内存中二叉搜索树,磁盘上多路树」这条经验规则的由来。

5.5 平衡树与有序映射

标准库中的有序映射(SortedMap / NavigableMap 一类接口)普遍以自平衡二叉搜索树为底层实现,原因有两点。

接口要求与 BST 能力一一对应。TreeMap 提供的 firstKey、lastKey、ceilingKey、floorKey、headMap、tailMap、subMap,正好是 BST 的最值查找、前驱后继查找与范围查询;keySet 的迭代顺序是按键升序,对应中序遍历。换成哈希表则其中任何一项都无法实现,这是哈希表在有序场景下不可替代的原因,其定位依据与代价见 哈希表。以字符串为键、查询以前缀与字典序为主时,另一种做法是按键的字符分层的字典树,见 字典树与字符串索引。

复杂度承诺需要一个带保证的树高。TreeMap 的文档承诺 get、put、remove 为 O(log n),这一承诺必须由结构本身提供,因此底层选择红黑树而不是普通 BST:红黑树用旋转与重新着色把树高限制在 2log₂(n+1) 以内,从而在概率之外给出确定性的上界。红黑树的五条性质、插入删除的调整规则、Comparator 与 equals 的一致性问题、各实现的复杂度对照,见 Java 集合框架实现原理 中 TreeMap 与 Set 系列部分。

一个使用层面的结论:需要「按键排序遍历」「取区间内的键」「找最接近的键」时选择有序映射,其余场景使用哈希表。有序性是额外的结构,必须用比较操作与 O(log n) 的常数去换。

6. 常见问题与排查

6.1 递归深度导致栈溢出

现象:处理大规模树时抛出 StackOverflowError(Java)或 RecursionError(Python);程序在执行到某处后直接崩溃,没有中间输出。

原因:递归遍历的栈深度等于树高。若树未做平衡且恰好由有序数据构造,树高等于节点数,递归深度也随之线性增长。Python 的默认递归深度上限约为 1000,Java 的线程栈默认容量约数百 KB 至 1 MB,深度通常在数千到数万量级耗尽;同时每层栈帧还保存局部变量,实际可用深度取决于栈帧大小。链表处理与树处理在这类问题是同源的,递归与迭代的取舍见 数组与链表。

排查:

  • 确认异常堆栈中是否出现同一个方法名重复成百上千层,这是递归过深的直接特征。
  • 估算树高:节点数与输入数据的顺序是否会导致单支形态;日志中是否出现退化的迹象(例如某次查找比较次数远超预期)。
  • 检查是否存在「本可剪枝却继续递归」的分支,例如深度限制参数未被传递。

修复方向:

  • 改用显式栈的迭代实现,把栈帧转移到堆上;Python 中也可通过 sys.setrecursionlimit 提高上限,但这只是把崩溃点推后,不解决问题。
  • 消除树高的线性来源:改用自平衡结构(或插入前打乱顺序),使树高回到 O(log n)。
  • 分治改为迭代、减少每层栈帧中的局部变量数量,可以延后但无法消除规模上限。

6.2 删除节点未正确接续子树

现象:删除后元素数量少于预期;遍历结果整段缺失;查找某个此前存在的键返回不存在;结构中不再满足 BST 约束。

原因:

  • 删除度为 1 的节点时,只把该节点从父节点的子引用上摘除,没有把它唯一的子树接续上去。
  • 递归删除时遗漏 root.left = delete(root.left, key) 的赋值,导致处理结果未被挂回。
  • 删除度为 2 的节点时替换了值,但忘记在右子树中真正删除后继节点,导致该值在树上出现两次。
  • 有父指针的实现中,接续子树后没有修正子树的 parent 指针。

排查:

  • 断言树的节点数与业务期望一致;遍历长度是比「包含某个键」更强的检查。
  • 用固定数据集删除后做一次中序遍历,检查是否严格递增——不递增说明结构已被破坏。
  • 专门覆盖四种用例:删除叶子、删除只有左子树的节点、删除只有右子树的节点、删除有两个子树的节点;再覆盖删到只剩一个节点与删除不存在的键。

防护:把全部结构修改收敛到少数几个方法中;删除接口统一返回新的子树根并由调用方挂接;有父指针时把「建立链接」与「修正父指针」写在相邻位置,避免分散。

6.3 BST 校验只比较子节点导致误判

现象:校验函数返回「合法」,但对该树做中序遍历得到的序列并不递增;或某个键在树中存在却查找不到。

原因:校验逻辑只比较节点与直接子节点的大小关系,而 BST 的约束作用于整棵子树。反例与正确写法见第三节 2.4 节。

排查与防护:

  • 用「中序序列严格递增」作为独立验证手段,与被测的校验函数交叉比对;两者结果不一致时,以中序序列为准。
  • 测试用例中必须包含「跨层违反约束但每层局部合法」的构造,如 10 → 右 15 → 15 的左 6。
  • 校验等值处理与插入时的等值约定是否一致:若插入允许等于(放在左侧或右侧),校验使用严格递增判断会把自己构造的树判为非法。

6.4 遍历顺序与预期不符

现象:输出序列与预期次序不一致;层序输出中不同层的节点混杂;后序输出实际得到前序。

原因:

  • 中序的迭代实现漏掉「当前节点为空但栈非空」的循环条件,导致右子树未被处理或顺序错乱。
  • 后序的迭代实现中,入栈顺序与结果插入位置未配合验证:写成「先压右后压左」再头插,得到的是前序而不是后序。
  • 层序遍历中没有在进入本层循环前固定层大小,导致跨层混合。
  • 递归实现中把访问语句放错位置(例如中序写成前序),三种次序的骨架完全相同,只有一行位置不同。

排查:用一个手工可验证的小树(三到七个节点的满二叉树)打印四种遍历结果,与手算结果逐一比对。遍历类缺陷在小规模用例上极易暴露,不需要构造复杂场景。

防护:为每一层输出标注层号;对层序结果断言每层长度;遍历结果与「按值排序后的结果」比对以验证中序在 BST 上的正确性。

6.5 序列化缺少空节点导致还原失败

现象:序列化与反序列化之后,树的形状与元素个数与原树不同;元素齐全但层次结构错误。

原因:序列化时省略空节点标记,反序列化时无法判断某个节点是否有左孩子,于是所有节点都被还原成「有左孩子」或「有右孩子」的固定形状。仅用单次遍历(前序、后序或层序)而无空节点标记时,多棵树共享同一份序列。

排查:

  • 对「只有右孩子的链」「只有左孩子的链」「左右不对称的树」分别做序列化—反序列化往返,比较结果是否与原树完全相同(结构与值都比)。
  • 检查序列长度的量级:前序加空节点标记的序列长度约为 2n,明显短于这个量级说明空节点被省略了。

防护:序列化协议中显式保留空节点标记;若为了压缩体积而省略,必须同时保存第二份信息(如中序序列或节点数),保证还原唯一;往返测试是这类缺陷的唯一可靠验证手段。

7. 检查清单

结构定义与边界:

  • 空树(根为空)在查找、插入、删除、遍历四个操作上的行为都已确定并测试。
  • 单节点树是叶子的特殊情况:遍历输出为单元素,删除后返回空,高度为 1。
  • 允许重复值的约定(小于等于放左还是放右)在所有操作中保持一致。
  • 需要区分「空节点」与「值为零的节点」时,不依赖值本身做判空。

递归实现:

  • 终止条件明确写出,且空节点的返回值与叶子节点的返回值已分别确定。
  • 返回值语义唯一:既表示子树答案,又供上层合并的量,其含义在函数注释中写明。
  • 每层是否有重复遍历(分开调用求高度之类的写法),能否合并为一次遍历。
  • 递归深度是否与树高绑定;输入可能导致树高为 O(n) 时改用显式栈。
  • 回溯场景中,修改与撤销严格配对,结果集合中保存的是路径副本而非引用。

指针与链接:

  • 插入与删除的返回值是否被赋回父节点的子引用(或已通过父指针正确挂接)。
  • 删除度为 1 的节点时,唯一的子树是否整段接续;删除度为 2 的节点时,后继节点是否被真正移除。
  • 有父指针时,所有结构修改处是否都同时维护了两个方向。
  • 接续子树后是否按要求断开被删节点的引用(在需要及时回收的语言中)。

二叉搜索树特有的正确性:

  • 校验用中序严格递增或上下界传递,而非只比较直接子节点。
  • 上下界的类型与初始值能覆盖最小与最大可能取值。
  • 范围查询是否利用了有序性剪枝,而不是全树遍历后过滤。
  • 前驱后继在「无子树」情形下的向上查找逻辑已单独测试。
  • 插入顺序是否可能有序;若可能,是否已改用平衡结构或打乱顺序。

序列化与遍历:

  • 序列化表示中是否保留了空节点信息,或另有信息保证还原唯一。
  • 序列化与反序列化的往返测试覆盖「单支链」与「左右不对称」两类形态。
  • 层序遍历的层大小在进入本层循环前固定。
  • 中序与后序的迭代实现已用小规模满二叉树手工验证顺序。

四、总结

二叉树解决的是线性结构无法表达的层次关系与分治结构问题。它把「每次比较后走到哪一半」这一决策过程从下标算术中独立出来,用显式的左右引用表示,交换到的是「插入删除不需要搬移元素」与「查找代价由比较路径长度决定」,代价是失去按位置的 O(1) 定位能力,并且查找代价依赖于树形。递归定义的树天然匹配递归算法,调用栈与显式栈的遍历在状态上同构,这一对应关系是树算法代码简短的根本原因。树与链表在节点结构与指针操作上同源,链接关系与存储代价的讨论见 数组与链表 与 抽象数据类型(ADT)。

结构与性质层面:

  • 度为 0 的节点数恒为度为 2 的节点数加 1,这条关系只依赖「除根外每个节点一个父节点」这一事实。
  • 高度 h 的二叉树节点数在 [h, 2^h − 1] 之间,n 个节点的高度在 [⌈log₂(n+1)⌉, n] 之间;完全二叉树达到高度下界,因此可以用数组存储并由下标算术给出父子关系。
  • 数组表示的空间代价由树高决定(O(2^h)),链式表示由节点数决定(O(n)),这是堆用数组而 BST 用链式的分界。
  • n 个节点有 2n 个引用字段,其中 n + 1 个为空;线索二叉树与莫里斯遍历都是对这部分空间的利用方式,后者不持久化修改,代价是每个节点的左子树最右链被走两遍。

遍历与还原层面:

  • 前序、中序、后序的区别只在「访问根」与「递归子树」的相对次序;选择依据是何时需要用到根的信息。层序用队列,空间为 O(w),与深优的 O(h) 是不同方向的界。
  • 递归遍历的空间等于树高,时间与树形无关(O(n));迭代实现不改变空间量级,只把栈帧从系统栈移到堆上。
  • 还原树形必须获得左右子树的规模分界,因此只有中序(或等价的划分信息)在场时结果唯一;前序加后序在单子节点处存在二义性。
  • 序列化必须处理空节点,否则还原不唯一;这是功能性缺陷而非输出格式问题。

二叉搜索树层面:

  • BST 的约束作用于整棵子树,中序遍历严格递增是其等价表述;校验必须用中序递增或上下界传递。
  • 查找、插入、删除的代价统一为 O(h),插入的路径唯一、新节点必为叶子;删除按度分三种情形,度为 2 时用前驱或后继替换并转化为前两种情形。
  • 范围查询的下界是结果规模 O(k),达到该界的做法是 O(log n + k) 的有序剪枝,而不是全树遍历。
  • 有序插入会构造出单支链,使复杂度从 O(log n) 退化为 O(n),且这种输入在实际数据中很常见,因此「是否可能有序插入」是设计阶段必须回答的问题。
  • 随机插入构造的 BST 期望高度约为 4.311 ln n ≈ 2.99 log₂n,平均查找代价约为 2 ln n ≈ 1.386 log₂n,两者都是 O(log n) 量级但常数不同,这一区别正是平均情况与最坏情况在树上的体现。

工程层面的三条判断:

  • 需要有序性时选择平衡树,其余场景选择哈希表。有序遍历、范围查询、前驱后继这三项能力是哈希表无法提供的,其代价是比较操作与 O(log n) 常数;标准库中的有序映射以红黑树实现,正是为了在概率之外给出树高的确定性上界,见 Java 集合框架实现原理。
  • 树的代价由树高决定,因此要把树高作为设计约束而不是运行结果。内存中的二叉结构可以用旋转、随机化或插入顺序约束控制树高;以块为单位访问的磁盘结构则必须改用多路平衡树降低层数,页大小与层高的关系见 mysql: 索引与执行计划。
  • 树的算法优化集中在两点:用返回值合并多项信息以避免重复遍历,用有序性或上下界剪枝以避免无效子树。前者把平衡判定从 O(n²) 降到 O(n),后者把范围查询从 O(n) 降到 O(log n + k),两者都建立在树的结构性质之上,而不是常数级的技巧。

复杂度记号与树高的关系、递归式的求解方法、以及复杂度相同而实测差异明显的成因,见 复杂度与算法分析;显式栈代替递归调用栈的机制、广度优先与队列的对应关系,见 栈与队列。