一、起源:从线性结构到层次结构
1.1 线性结构在层次关系上的不足
数组与链表描述的是「一个元素至多有一个前驱、一个后继」的关系,见 数组与链表。这种一对一的关系能够表达序列,却不能表达包含与从属。
层次关系的特征是「一对多」:一个整体由若干部分组成,每个部分又可以继续细分。文件系统、组织架构、算术表达式、语法结构、分类体系都属于这一类。用线性结构表达它,只有两种办法,代价都很明显。
把层次压平成序列。例如用「先根序列」记录路径,每个元素前面附带层号或父节点下标。这种表示可以存储,但层次信息被降级为附加字段,任何与层次相关的操作(求祖先、求子树、求深度)都需要重新扫描整个序列,无法利用关系本身的结构。
用引用字段显式编码关系。例如在数组之外为每个元素记录一个父节点下标。这实际上已经在构建非线性的关系,只是没有把它作为独立的逻辑结构看待。一个父子关系的集合,其形态就是树。
树之所以独立于线性表,在于关系的存储方式发生了变化:线性表中位置由下标或前驱指针唯一确定,树中每个节点需要保存多个后继的入口。这一差别带来的直接后果是——定位不再是「走固定步数」,而是「在每一步选择走哪个分支」,选择过程本身可以携带比较信息。
1.2 分治查找对结构的要求
在有序数组中查找一个元素,二分查找每次比较可以把候选范围缩小一半,代价为 O(log n)。它能够这样做的前提有两个:
- 元素有序,比较结果给出了「目标在左半还是右半」的信息。
- 中间位置可以 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
三个性质使数组表示在完全二叉树上优于链式表示:
- 没有引用字段,空间利用率最高,只有数据本身;
- 下标算术代替指针追逐,父子访问是相邻或按公式跳转,缓存局部性远好于链式;
- 层序即数组顺序,不需要队列即可按层处理。
代价出现在形态不完整时。数组必须为「按完全二叉树编号后可能出现的所有位置」预留槽位,因此
完全二叉树: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),两者都建立在树的结构性质之上,而不是常数级的技巧。
复杂度记号与树高的关系、递归式的求解方法、以及复杂度相同而实测差异明显的成因,见 复杂度与算法分析;显式栈代替递归调用栈的机制、广度优先与队列的对应关系,见 栈与队列。