二叉搜索树（BST 操作 · 验证 · 转化）

BST 核心性质

• 中序遍历 = 升序序列
• 每个节点：左子树所有值 < 根值 < 右子树所有值
• 搜索/插入/删除时间：平均 O(logn)，最坏 O(n)（退化为链表）

BST 搜索

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

BST 插入（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;
}

BST 删除（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 min = root.right;
        while (min.left != null) min = min.left;
        root.val = min.val;
        root.right = deleteNode(root.right, min.val);
    }
    return root;
}

验证 BST（LeetCode 98）

中序遍历应严格递增，或用范围递归：

// 方法1：范围递归（更清晰）
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);
}

// 方法2：中序遍历，记录前一个值
long prev = Long.MIN_VALUE;
boolean isValidBSTInorder(TreeNode root) {
    if (root == null) return true;
    if (!isValidBSTInorder(root.left)) return false;
    if (root.val <= prev) return false;
    prev = root.val;
    return isValidBSTInorder(root.right);
}

BST 的第 K 小元素（LeetCode 230）

中序遍历，计数器 k--，到 0 时返回：

int ans = 0, count = 0;
int kthSmallest(TreeNode root, int k) {
    count = k;
    inorder(root);
    return ans;
}
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (--count == 0) { ans = node.val; return; }
    inorder(node.right);
}

有序数组转平衡 BST（LeetCode 108）

取中间元素为根，递归建树：

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

BST 转累加树（LeetCode 538）

反向中序（右 → 根 → 左），累加前缀和：

int sum = 0;
TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    convertBST(root.right);
    root.val += (sum += root.val) - root.val;  // 简写：sum += root.val; root.val = sum;
    convertBST(root.left);
    return root;
}