专题 18二叉搜索树：有序性带来的降维打击

18.1BST 的性质：中序遍历即有序

很多同学第一次听说 BST 会想：「不就是棵树吗，凭什么它比普通二叉树高级？」答案就在它的一条定义上。一棵合法的二叉搜索树要求：对于树上任意一个节点，它的左子树里所有节点的值都严格小于它，右子树里所有节点的值都严格大于它（有些教材允许等于，力扣默认不允许重复值，用严格不等）。换句话说，整棵树满足「左 ≤ 根 ≤ 右」的全局秩序。

一棵合法的 BST 长这样（数值已标好）：
        8
      /   \
     3     10
    / \      \
   1   6      14
      / \     /
     4   7   13

随手抽查几个节点都满足「左边全小、右边全大」：
  - 根 8：左边 3/1/6/4/7 全 < 8；右边 10/14/13 全 > 8 ✓
  - 节点 3：左边 1 < 3；右边 6/4/7 全 > 3 ✓
  - 节点 10：右边 14/13 全 > 10；左边没有，默认满足 ✓

两大武器，记住这八个字就够

BST 之所以好用，是因为这条秩序带来了两件普通二叉树没有的「外挂」：

• 武器一：中序遍历 = 升序数组。「左 → 根 → 右」的访问顺序，刚好就是「小的先访问、大的后访问」，于是 BST 的中序遍历结果天然是一个从小到大排好序的序列。这招在「第 K 小」「判断是否合法」「转成有序结构」等题里反复救场。
• 武器二：查找只需走单边，复杂度 O(h)。要找某个值 val，从根开始：val 比当前节点小就只走左边，大就只走右边。每一步都砍掉一半子树，完全不用回头。最坏情况退化成链时是 O(n)，平衡 BST 是 O(log n)（h 是树高）。

用武器二在上面的树里找 7：
  8 → 7<8 走左 → 到 3
  3 → 7>3 走右 → 到 6
  6 → 7>6 走右 → 到 7，命中！
只走了 4 步，根本没碰右边的 10/14/13。这就是「走单边」的威力。

节点定义（后面所有题都基于它）

力扣里树节点就长这样，和专题 07完全一致，这里再贴一遍方便对照：

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;
    }
}

18.2验证二叉搜索树（中等，力扣 98）

中等 核心：递归时把「上下界」一路传下去

题意：给你一棵二叉树，判断它是不是一棵有效的二叉搜索树。有效 BST 的定义前面讲过：每个节点的左子树全部小于它、右子树全部大于它，且左右子树自身也得是 BST；空树算合法。例如 [2,1,3] 是 BST，[5,1,4,null,null,3,6] 不是。

思路推导：为什么「只比较父子」是错的

最直觉的写法：遍历每个节点，只要它比左孩子大、比右孩子小就放心。代码大概是：

错误思路（伪代码）：
boolean check(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 check(node.left) && check(node.right)

这个写法只看节点和它的直接孩子，漏掉了对「祖先」的约束。力扣 98 官方给的经典反例 [5,1,4,null,null,3,6] 在根节点就露馅（右孩子 4 比根 5 还小）；但更隐蔽的是下面这棵，父子比较全部通过，却仍然不是 BST：

        10
       /  \
      5   15
          /
         6
父子检查：10 比 5 大、比 15 小 ✓；15 比 6 大 ✓；5、6 都没孩子 ✓
看似全过，但 6 在 10 的右子树里，按 BST 铁律必须 > 10，而 6 < 10 → 非法！
「只比父子」完全没发现这个矛盾，因为它忘了：6 身上还压着「祖先 10 定下的下界」。

所以正确的思路是：每个节点都必须落在一个由祖先不断收窄的区间 (lower, upper) 里。当你从左孩子下来，说明当前节点必须比父节点小，于是它的上界 upper 收紧成父节点的值；从右孩子下来，下界 lower 抬升成父节点的值。把这对上下界一路递归传下去，任何一次越界就说明不合法。

把 (lower, upper) 传下去的过程（用上面 6 的反例）：
  根 10：区间 (-∞, +∞)，10 在里 ✓
    左 5：区间 (-∞, 10)，5 在里 ✓
    右 15：区间 (10, +∞)，15 在里 ✓
      15 的左 6：区间 (10, +∞)（继承了祖先 10 定的下界！），但 6 < 10 → 越界，判非法 ✓
看，把祖先的界传下来，6 立刻被抓住。

参考代码

class Solution {
    public boolean isValidBST(TreeNode root) {
        // 初始区间用 Long 的边界，因为节点值可能正好踩到 Integer 的边界（详见 18.7）
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // lower / upper 是「当前节点允许取值的开区间」
    private boolean dfs(TreeNode node, long lower, long upper) {
        if (node == null) return true;          // 空子树永远是合法 BST
        // 当前节点必须严格落在 (lower, upper)，等于也不行（力扣默认无重复值）
        if (node.val <= lower || node.val >= upper) return false;
        // 左子树：上界收紧为 node.val；右子树：下界抬升为 node.val
        return dfs(node.left, lower, node.val)
            && dfs(node.right, node.val, upper);
    }
}

复杂度

每个节点只访问一次，每次 O(1) 比较，时间 O(n)，空间是递归栈 O(h)（h 为树高，最坏退化 O(n)）。这比「先中序遍历再检查是否升序」的 O(n) 额外数组空间更省，且能提前剪枝。

18.3二叉搜索树中的搜索（简单，力扣 700）

简单 核心：利用有序性，每步砍掉一半

题意：给定一棵二叉搜索树的根 root 和一个目标值 val，请你在树里找到值为 val 的节点并返回它的子树；找不到就返回 null。例如树 [4,2,7,1,3] 找 2，返回以 2 为根的子树（包含 1 和 3）。

思路推导：别遍历，要「二分」

如果这是一棵普通二叉树，你只能老老实实遍历所有节点，O(n)。但这是 BST！回忆武器二：val 比当前节点小，目标一定在左子树；大，一定在右子树。所以每一步都直接决定往哪边走，另一半根本不用看——这就是树上的「二分查找」。

用递归还是循环？两者都行。递归就是「把走单边」这句话翻译成代码；循环则更省栈空间、更好写。下面用循环写，思路更直白：从根出发，比大小决定下一脚踩左边还是右边，碰到 null 说明这条路走到头了，树里没有 val。

在 [4,2,7,1,3] 里找 7：
  4 → 7>4 走右 → 到 7，命中，返回以 7 为根的子树
在 [4,2,7,1,3] 里找 5：
  4 → 5>4 走右 → 7 → 5<7 走左 → 左是 null → 没找到，返回 null

参考代码

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;                            // 走到叶子还没碰到，说明不存在
    }
}

复杂度

每步砍掉一半子树，最多走树高 h 步，时间 O(h)（平衡树 O(log n)，最坏退化 O(n)），空间 O(1)。这就是 BST 查找相比普通树的降维优势。

18.4将有序数组转换为二叉搜索树（简单，力扣 108）

简单 核心：取中点当根，左右半边各建子树

题意：给你一个升序排列的整数数组 nums，请你把它转换成一棵「高度平衡」的二叉搜索树，并返回根节点。高度平衡指每个节点的左右子树高度差不超过 1。例如 nums = [-10,-3,0,5,9]，一种合法答案是 [0,-3,9,-10,null,5]。

思路推导：从「数组有序」想到「BST 中序有序」

已知两件事：(1) 数组是升序的；(2) BST 的中序遍历也是升序的。那是不是「数组就是某棵 BST 的中序序列」？是的！问题于是变成：已知中序序列，怎么还原出一棵树，而且还要平衡？

中序序列决定了「谁在谁左边、谁在谁右边」，但没决定「谁是根」。根选哪里，整棵树的形状就由哪里切开。要让树平衡，最自然的切法就是每次取中点当根：

• 中点左边的所有元素都比它小 → 天然构成左子树的中序序列；
• 中点右边的所有元素都比它大 → 天然构成右子树的中序序列；
• 左右半边长度几乎相等，所以递归下去左右子树高度差不超过 1，自动平衡。

nums = [-10, -3, 0, 5, 9]，长度 5，中点下标 2 = 0 当根：
        0
      /   \
  左半[-10,-3]  右半[5,9]
  左半中点 -3 当根，左挂 -10 →   右半中点 9 当根，左挂 5 →
        0
      /   \
    -3     9
    /     /
  -10    5
中序走一遍：-10,-3,0,5,9 正好是原数组，且左右高度差 ≤ 1 ✓

为什么中点能保证平衡？因为每次把区间从正中间劈成两半，左右子树分到的元素数量最多差 1，递归深度自然就是 log n 级别，不会退化成链。注意中点可以「偏左」或「偏右」（比如区间长度偶数时有两个候选中点），两种都合法，题目也接受任意一种。

参考代码

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

    // 用闭区间 [lo, hi] 表示「当前要建的子树对应的数组片段」
    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) return null;                 // 区间为空，返回空树
        int mid = lo + (hi - lo) / 2;             // 中点当根（这样写防 (lo+hi) 溢出）
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, lo, mid - 1);     // 左半边是左子树
        root.right = build(nums, mid + 1, hi);    // 右半边是右子树
        return root;
    }
}

复杂度

每个数组元素恰好当一次根，建树 O(n)；递归栈深度为树高 O(log n)（平衡）。返回的就是高度平衡的 BST，满足题目要求。

18.5二叉搜索树中第 K 小的元素（中等，力扣 230）

中等 核心：中序遍历数到第 K 个

题意：给定一棵二叉搜索树的根和一个整数 k，返回树中第 k 小的元素（1-based）。例如树 [3,1,4,null,2]，中序是 [1,2,3,4]，k=1 返回 1，k=3 返回 3。

思路推导：中序第 K 个 = 第 K 小

普通无序数组找第 k 小，得排序或快选（见专题 16）。但这是 BST！武器一告诉我们：BST 的中序遍历天然升序。升序序列里的第 k 个，不就是第 k 小吗？所以这条路简直是量身定做——

顺着中序顺序（左 → 根 → 右）走，每访问一个节点就计数 +1，数到 k 的瞬间，那个节点的值就是答案。不需要把整棵树都遍历完，数到了就可以停（提前返回能省时间，尤其 k 很小时）。

树 [3,1,4,null,2]，中序访问顺序：1(计数1) → 2(计数2) → 3(计数3) → 4(计数4)
k=3：数到第三个节点是 3，直接返回，不用再访问 4。

为什么不用「先收集成数组再取 arr[k-1]」？那样空间 O(n)。用递归计数 + 提前返回，空间只有栈 O(h)，更优雅。两种都能过，下面给「计数 + 提前停」的写法。

参考代码

class Solution {
    private int count;     // 已经中序访问了多少个节点
    private int ans;       // 第 k 小的答案

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

    private void inorder(TreeNode node, int k) {
        if (node == null || count >= k) return;   // 空 或 已经数够就别再走了
        inorder(node.left, k);                    // 先左
        count++;                                  // 访问当前（根）
        if (count == k) { ans = node.val; return; } // 正好第 k 个，记下并停
        inorder(node.right, k);                   // 再右
    }
}

复杂度

平均访问 k 个节点就停，时间约 O(h + k)（h 是到目标节点的深度）；最坏 k=n 时 O(n)。空间 O(h) 递归栈。比「全收集再取」省空间，且提前返回更快。

18.6删除二叉搜索树中的节点（中等，力扣 450）

中等 核心：删完用「中序后继」顶替，保住 BST 性质

题意：给定一棵 BST 的根和一个值 key，删掉值为 key 的节点，并且保证删除后仍然是一棵合法的 BST，返回新的根。例如 [5,3,6,2,4,null,7] 删 3，返回 [5,4,6,2,null,null,7] 之类（删法不唯一但都合法）。

思路推导：删除的难处在「别破坏秩序」

查找很简单（走单边，见 18.3）。真正的麻烦是：删掉一个节点后，它下面的子树怎么接回去，才能不破坏「左小右大」？按「要删节点的孩子情况」分三种：

• 情况一：没有左孩子。很省事，直接用右孩子（可能也是 null）顶替当前位置即可，右边本来就都比当前大，接上去仍合法。
• 情况二：没有右孩子。对称，用左孩子顶替。
• 情况三：左右孩子都有（最棘手）。你不能随便用左孩子或右孩子顶，因为那样会丢掉另一半子树。正确做法是：找一个「值最合适」的节点来替代当前节点，让它同时满足「比左子树都大、比右子树都小」。谁是这个人选？中序后继（in-order successor）——也就是右子树里最左边的那个节点，它是右子树里最小的值，自然大于左子树全部、小于右子树剩余部分。

删 5（左右都有）的例子：
        5
      /   \
     3     8
    / \   / \
   2   4 6   9
右子树最左下是 6（右子树里最小的），用 6 顶替 5：
        6
      /   \
     3     8
    / \   / \
   2   4 7   9      （原 6 被抽走，6 的右孩子 7 接回 8 的左）
为什么是 6？因为 6 是「大于左子树(2,3,4)、小于右子树其余(7,8,9)」的唯一值，顶上后仍合法。

为什么「用中序后继顶替」能保持 BST 性质？因为中序后继是右子树的最小值，它满足：大于当前节点的所有左后代、小于右子树里除它以外的所有节点。把它的值复制到当前节点，再递归地把「后继」从右子树里删掉（后继至多只有一个右孩子，落回情况一/二很好处理），整棵树秩序纹丝不动。

参考代码

class Solution {
    public 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 {
            // 找到要删的节点就是 root，分三种情况
            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 = deleteNode(root.right, succ.val);
        }
        return root;                                    // 把接好的子树交回上层
    }
}

复杂度

查找要删节点走单边 O(h)；找后继沿右子树最左走也是 O(h)；总复杂度 O(h)（h 为树高）。空间 O(h) 递归栈。关键点在于「递归地把子树重新接回」——这正是专题 07分解式思想的体现：左右子树干完删除，把结果交回给我。

18.7本专题常见坑

18.8自测题