第22篇-二叉搜索树-有序结构下的查找-插入-删除与验证

上一篇我们学习了二叉树经典题型，包括层序遍历、最大深度和路径问题。

这些题主要依赖的是二叉树的结构：

当前节点 + 左子树 + 右子树

这一篇我们继续学习一种更特殊的二叉树：二叉搜索树。

二叉搜索树英文是 Binary Search Tree，常简称为 BST。
它比普通二叉树多了一个非常重要的性质：

左子树所有节点值 < 当前节点值 < 右子树所有节点值

正是因为这个有序性质，BST 可以高效支持：

• 查找某个值
• 插入新节点
• 删除指定节点
• 验证一棵树是否为 BST
• 找第 k 小元素
• 求有序序列中的前驱和后继

很多 BST 题看起来是树题，本质上其实是在利用“有序”做剪枝。

学完这篇，你应该能理解 BST 的核心性质，并能独立写出查找、插入、验证和删除的基础代码。

基础准备：二叉树节点定义

本文仍然使用常见的二叉树节点定义：

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

TreeNode() {
}

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

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

在多数算法平台中，TreeNode 会提前给出，刷题时只需要写 Solution 类中的方法。

核心概念：BST 到底满足什么性质

二叉搜索树的定义是：

对于任意一个节点：
左子树中所有节点的值都小于它
右子树中所有节点的值都大于它
并且左右子树本身也都是二叉搜索树

例如下面这棵树就是 BST：

5
/ \\
3 7
/ \\ / \\
2 4 6 8

对节点 5 来说：

• 左子树节点 2、3、4 都小于 5
• 右子树节点 6、7、8 都大于 5

对节点 3 来说：

• 左子树节点 2 小于 3
• 右子树节点 4 大于 3

每一个节点都满足这个规则，所以它是一棵 BST。

不是只比较左右节点

下面这棵树看起来局部没问题，但不是 BST：

5
/ \\
3 7
/
4

节点 7 的左子节点 4 小于 7，局部看没错。
但 4 位于 5 的右子树中，它必须大于 5。

因为：

右子树所有节点都要大于根节点

而 4 < 5，所以这棵树不是 BST。

BST 的约束不是“左子节点小、右子节点大”，而是“左子树全部小、右子树全部大”。

中序遍历：BST 最重要的隐藏线索

BST 有一个非常重要的结论：

对 BST 做中序遍历，结果一定是升序序列

中序遍历顺序是：

左子树 -> 当前节点 -> 右子树

由于 BST 满足：

左子树 < 当前节点 < 右子树

所以中序遍历刚好会从小到大访问节点。

例如：

5
/ \\
3 7
/ \\ / \\
2 4 6 8

中序遍历结果是：

2, 3, 4, 5, 6, 7, 8

这个性质非常常用，很多 BST 题都可以转化为：

在一棵树上得到一个有序序列

中序遍历代码

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inorder(root, ans);
return ans;
}

private void inorder(TreeNode root, List<Integer> ans) {
if (root == null) {
return;
}

inorder(root.left, ans);
ans.add(root.val);
inorder(root.right, ans);
}
}

普通二叉树中序遍历只是遍历顺序，BST 中序遍历会得到升序结果。

题型一：在 BST 中查找一个值

题目：

给定 BST 的根节点 root 和一个整数 val，如果树中存在值为 val 的节点，返回该节点；否则返回 null。

如果是普通二叉树，想找一个值可能需要遍历所有节点。

但 BST 可以利用有序性质：

• 如果 val == root.val，找到目标
• 如果 val < root.val，只可能在左子树
• 如果 val > root.val，只可能在右子树

这样每次都可以排除一半方向。

递归写法

class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}

if (root.val == val) {
return root;
}

if (val < root.val) {
return searchBST(root.left, val);
}

return searchBST(root.right, val);
}
}

迭代写法

class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode cur = root;

while (cur != null) {
if (cur.val == val) {
return cur;
}

if (val < cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}

return null;
}
}

复杂度分析

如果树比较平衡，每次大约排除一半节点：

时间复杂度：O(log n)

如果树退化成链表：

时间复杂度：O(n)

空间复杂度：

• 递归写法：O(h)，h 是树高
• 迭代写法：O(1)

查找时根据目标值和当前节点值的大小关系，只走左边或右边。

题型二：向 BST 中插入一个值

题目：

给定 BST 的根节点 root 和一个整数 val，将 val 插入到 BST 中，并返回插入后的根节点。

插入和查找很像。

我们从根节点开始：

• 如果 val < root.val，应该插入左子树
• 如果 val > root.val，应该插入右子树
• 直到遇到空位置，把新节点放进去

递归写法

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}

if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}

return root;
}
}

为什么要写 root.left = …

很多初学者会写成：

insertIntoBST(root.left, val);

这样在递归走到空节点并创建新节点后，父节点并没有接住这个新节点。

正确写法必须是：

root.left = insertIntoBST(root.left, val);

或者：

root.right = insertIntoBST(root.right, val);

因为递归函数返回的是插入完成后的子树根节点。

迭代写法

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}

TreeNode cur = root;

while (true) {
if (val < cur.val) {
if (cur.left == null) {
cur.left = new TreeNode(val);
break;
}
cur = cur.left;
} else {
if (cur.right == null) {
cur.right = new TreeNode(val);
break;
}
cur = cur.right;
}
}

return root;
}
}

关于重复值

不同题目对重复值的定义可能不同：

• 有些题保证插入值不存在
• 有些 BST 约定重复值放右子树
• 有些 BST 不允许重复值

LeetCode 常见 BST 验证题通常使用严格不等：

左子树所有值 < 当前节点值 < 右子树所有值

所以本文默认不讨论重复值。如果题目允许重复值，要按照题目规则修改判断条件。

插入就是按大小关系一路查找空位置，最后把新节点接到父节点下面。

题型三：验证一棵树是否为 BST

题目：

给定一棵二叉树，判断它是否是有效的二叉搜索树。

这是 BST 中非常高频、也非常容易写错的题。

错误思路：只比较左右子节点

很多人会写出类似代码：

if (root.left != null && root.left.val >= root.val) {
return false;
}
if (root.right != null && root.right.val <= root.val) {
return false;
}

这只能保证当前节点和左右孩子之间满足大小关系。
但 BST 要求的是：

整棵左子树都小于当前节点
整棵右子树都大于当前节点

前面提到的例子：

5
/ \\
3 7
/
4

局部比较能通过，但它不是 BST。

验证方法一：上下界递归

验证 BST 时，可以给每个节点规定一个允许范围。

例如根节点 5：

左子树所有节点必须在 (-∞, 5) 范围内
右子树所有节点必须在 (5, +∞) 范围内

对右子树节点 7 来说，它的左子节点虽然要小于 7，但仍然必须大于 5。

所以节点 7 的左子树范围是：

(5, 7)

Java 代码实现

class Solution {
public boolean isValidBST(TreeNode root) {
return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean check(TreeNode root, long lower, long upper) {
if (root == null) {
return true;
}

if (root.val <= lower || root.val >= upper) {
return false;
}

return check(root.left, lower, root.val)
&& check(root.right, root.val, upper);
}
}

为什么用 long

节点值可能等于 Integer.MIN_VALUE 或 Integer.MAX_VALUE。

如果上下界使用 int，边界处理容易出错。

所以更稳的做法是使用：

Long.MIN_VALUE
Long.MAX_VALUE

这样可以安全覆盖所有 int 范围内的节点值。

每个节点不仅要和父节点比较，还要落在祖先节点共同限制出的范围内。

验证方法二：中序遍历检查升序

BST 的中序遍历一定是严格升序。

所以我们也可以在中序遍历过程中，检查当前值是否大于前一个访问到的值。

Java 代码实现

class Solution {
private Long prev = null;

public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}

if (!isValidBST(root.left)) {
return false;
}

if (prev != null && root.val <= prev) {
return false;
}
prev = (long) root.val;

return isValidBST(root.right);
}
}

代码怎么理解

中序遍历的顺序是：

左 -> 根 -> 右

如果这棵树是 BST，那么每次访问到的新节点值，都必须比上一个节点值更大。

prev 用来保存上一次访问到的节点值。

一旦发现：

root.val <= prev

就说明中序序列不是严格升序，直接返回 false。

两种验证方法怎么选

两种都很重要。
如果只记一种，优先记上下界递归，因为它更直接体现 BST 的全局约束。

题型四：删除 BST 中的节点

目录中提到 BST 的查找、删除和验证。
删除比查找、插入稍微复杂一些，因为删除节点后仍然要保持 BST 性质。

题目：

给定 BST 的根节点 root 和一个值 key，删除值为 key 的节点，并返回删除后的根节点。

删除可以分情况讨论。

情况一：没有找到目标节点

如果 root == null，说明树中没有这个值，直接返回 null。

情况二：目标值小于当前节点

目标节点只可能在左子树：

root.left = deleteNode(root.left, key);

情况三：目标值大于当前节点

目标节点只可能在右子树：

root.right = deleteNode(root.right, key);

情况四：找到目标节点

找到目标节点后，还要分三种情况：

• 没有左子节点：返回右子节点
• 没有右子节点：返回左子节点
• 左右子节点都有：找右子树中的最小节点替换当前节点

右子树中的最小节点，就是当前节点的中序后继。

Java 代码实现

class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}

if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
}

if (key > root.val) {
root.right = deleteNode(root.right, key);
return root;
}

if (root.left == null) {
return root.right;
}

if (root.right == null) {
return root.left;
}

TreeNode successor = findMin(root.right);
root.val = successor.val;
root.right = deleteNode(root.right, successor.val);

return root;
}

private TreeNode findMin(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
}

为什么可以用后继节点替换

如果一个节点左右子树都存在，直接删除它会断开两边子树。

更稳的做法是：

右子树最小节点一定满足：

大于左子树所有节点
小于右子树中其他节点

所以用它替换当前节点后，BST 性质仍然成立。

删除有两个子节点的节点时，常用右子树最小节点或左子树最大节点替换。

题型五：BST 中第 k 小的元素

这是中序遍历性质的典型应用。

题目：

给定 BST 的根节点和整数 k，返回第 k 小的节点值。

由于 BST 中序遍历是升序序列，所以第 k 小元素就是中序遍历访问到的第 k 个元素。

Java 代码实现

class Solution {
private int count = 0;
private int ans = 0;

public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return ans;
}

private void inorder(TreeNode root, int k) {
if (root == null) {
return;
}

inorder(root.left, k);

count++;
if (count == k) {
ans = root.val;
return;
}

inorder(root.right, k);
}
}

一个小优化

上面的代码找到答案后，当前递归层会返回，但外层递归还可能继续执行。

可以加一个判断提前停止：

if (count >= k) {
return;
}

完整写法：

class Solution {
private int count = 0;
private int ans = 0;

public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return ans;
}

private void inorder(TreeNode root, int k) {
if (root == null || count >= k) {
return;
}

inorder(root.left, k);

count++;
if (count == k) {
ans = root.val;
return;
}

inorder(root.right, k);
}
}

BST 的第 k 小问题，本质就是中序遍历访问第 k 个节点。

查找前驱和后继：理解有序结构的延伸

在 BST 中：

• 前驱：小于当前值的最大节点
• 后继：大于当前值的最小节点

例如：

5
/ \\
3 7
/ \\ / \\
2 4 6 8

对于节点 5：

• 前驱是 4
• 后继是 6

这和有序数组很像：

2, 3, 4, 5, 6, 7, 8

只是 BST 把有序关系存放在树结构里。

找大于目标值的最小节点

class Solution {
public TreeNode findSuccessor(TreeNode root, int target) {
TreeNode ans = null;
TreeNode cur = root;

while (cur != null) {
if (cur.val > target) {
ans = cur;
cur = cur.left;
} else {
cur = cur.right;
}
}

return ans;
}
}

代码怎么理解

如果 cur.val > target，说明 cur 可能是答案。
但为了找到更小的合法值，还要继续往左走。

如果 cur.val <= target，说明当前节点和左子树都不可能成为后继，只能往右走。

这种写法和二分查找中的“寻找第一个大于目标值的位置”非常像。

BST 和普通二叉树：做题思路对比

可以简单记成：

普通二叉树靠遍历，二叉搜索树靠有序

常见坑点：BST 题最容易错在哪里

1. 验证 BST 时只比较左右子节点

错误原因是忽略了祖先节点对当前节点的限制。

正确做法应该是：

check(root, lower, upper)

每个节点都必须落在合法范围内。

2. 忘记 BST 中序遍历必须严格升序

如果题目不允许重复值，判断时应该使用：

root.val <= prev

而不是只判断：

root.val < prev

因为相等也不符合严格 BST。

3. 上下界使用 int 导致边界错误

如果节点值等于 Integer.MIN_VALUE 或 Integer.MAX_VALUE，使用 int 边界可能误判。

更稳的写法是：

Long.MIN_VALUE
Long.MAX_VALUE

4. 插入节点时没有接回子树

递归插入时必须写：

root.left = insertIntoBST(root.left, val);

不能只调用递归函数却不接收返回值。

5. 删除两个孩子的节点时直接乱接子树

删除有两个孩子的节点时，推荐使用：

• 右子树最小节点
• 或左子树最大节点

不要随意把左子树或右子树挂到某个位置，否则容易破坏 BST 性质。

6. 忽略树退化成链表的情况

BST 的查找、插入、删除在平衡时是 O(log n)。

但如果树长这样：

1
\\
2
\\
3
\\
4

它已经退化成链表，操作复杂度会变成 O(n)。

复杂度分析：BST 操作到底快在哪里

设二叉搜索树节点数为 n，树高为 h。

大多数 BST 操作复杂度都和树高有关：

如果 BST 比较平衡：

h = log n

查找、插入、删除就是：

O(log n)

如果 BST 退化成链表：

h = n

这些操作会退化为：

O(n)

这也是为什么实际工程里经常使用平衡二叉搜索树，例如红黑树、AVL 树等。

模板总结：BST 高频代码怎么记

查找模板

while (root != null) {
if (root.val == target) {
return root;
}

if (target < root.val) {
root = root.left;
} else {
root = root.right;
}
}

return null;

插入模板

if (root == null) {
return new TreeNode(val);
}

if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else if (val > root.val) {
root.right = insertIntoBST(root.right, val);
}

return root;

验证模板

boolean check(TreeNode root, long lower, long upper) {
if (root == null) {
return true;
}

if (root.val <= lower || root.val >= upper) {
return false;
}

return check(root.left, lower, root.val)
&& check(root.right, root.val, upper);
}

中序遍历模板

void inorder(TreeNode root) {
if (root == null) {
return;
}

inorder(root.left);
visit(root);
inorder(root.right);
}

总结

二叉搜索树是建立在普通二叉树基础上的有序结构。
它的题目不只是考树遍历，更重要的是考你能不能利用“左小右大”的性质减少不必要的搜索。

你可以重点记住下面几句话：

• BST 的核心性质是左子树全部小于根，右子树全部大于根
• 这个性质对每一个节点都成立
• 验证 BST 不能只比较左右孩子
• BST 的中序遍历一定是严格升序
• 查找时根据大小关系只走一边
• 插入时一路找到空位置并接上新节点
• 删除有两个孩子的节点时，可以用右子树最小节点替换
• 第 k 小元素可以通过中序遍历解决
• BST 操作复杂度取决于树高
• 退化 BST 的性能可能变成 O(n)