二叉搜索树（BST）：核心操作与经典题

BST 的性质

中序遍历 BST 得到严格递增序列，这是解 BST 题的关键武器。

      5
     / \
    3   7
   / \   \
  2   4   8

中序：2, 3, 4, 5, 7, 8（递增）

基本操作

查找（LeetCode 700）

TreeNode searchBST(TreeNode root, int val) {
    if (root == null) return null;
    if (val == root.val) return root;
    return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}

插入（LeetCode 701）

TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);  // 找到插入位置
    if (val < root.val) root.left = insertIntoBST(root.left, val);
    else root.right = insertIntoBST(root.right, val);
    return root;
}

删除（LeetCode 450）

删除分三种情况：

1. 叶子节点：直接删除
2. 有一个子节点：用子节点替代
3. 有两个子节点：用右子树最小节点（中序后继）替代

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) {
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        root.right = deleteNode(root.right, key);
    } else {
        // 找到了要删除的节点
        if (root.left == null) return root.right;   // 无左子树
        if (root.right == null) return root.left;   // 无右子树
        // 有两个子节点：找右子树最小值
        TreeNode minNode = getMin(root.right);
        root.right = deleteNode(root.right, minNode.val);
        minNode.left = root.left;
        minNode.right = root.right;
        root = minNode;
    }
    return root;
}

TreeNode getMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

验证 BST

验证是否是合法 BST（LeetCode 98）

常见错误：仅比较节点与左右子节点，忽略上界/下界约束。

boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val)   // 左子树上界变为当前节点
        && validate(node.right, node.val, max); // 右子树下界变为当前节点
}

另一种方法（中序遍历）：中序遍历应严格递增：

long prev = Long.MIN_VALUE;
boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!isValidBST(root.left)) return false;
    if (root.val <= prev) return false;  // 不严格递增
    prev = root.val;
    return isValidBST(root.right);
}

利用中序遍历

第 k 小的元素（LeetCode 230）

int count = 0, result = 0;
int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}

void inorder(TreeNode node, int k) {
    if (node == null) return;
    inorder(node.left, k);
    if (++count == k) { result = node.val; return; }
    inorder(node.right, k);
}

BST 中的众数（LeetCode 501）

不使用额外空间，在中序遍历时用 prev 指针比较：

int maxCount = 0, count = 0;
Integer prev = null;
List<Integer> modes = new ArrayList<>();

int[] findMode(TreeNode root) {
    inorder(root);
    return modes.stream().mapToInt(Integer::intValue).toArray();
}

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (prev != null && prev == node.val) count++;
    else count = 1;
    if (count > maxCount) { maxCount = count; modes.clear(); modes.add(node.val); }
    else if (count == maxCount) modes.add(node.val);
    prev = node.val;
    inorder(node.right);
}

构造 BST

从有序数组构造平衡 BST（LeetCode 108）

TreeNode sortedArrayToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}

TreeNode build(int[] nums, int l, int r) {
    if (l > r) return null;
    int mid = l + (r - l) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = build(nums, l, mid - 1);
    root.right = build(nums, mid + 1, r);
    return root;
}

把 BST 转换为累加树（LeetCode 538）

      5                 18
     / \               / \
    3   7     -->    21   15
   / \   \          / \     \
  2   4   8        24  21   13

从右到左中序遍历（逆中序），维护前缀和：

int sum = 0;
TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    convertBST(root.right);   // 先遍历右子树
    sum += root.val;
    root.val = sum;
    convertBST(root.left);
    return root;
}

总结