【LeetCode算法题精讲】二叉搜索树（BST）精讲：验证二叉搜索树 + 二叉搜索树的最近公共祖先

2401_88352165

374人浏览 · 2026-08-17 15:08:11

2401_88352165 · 2026-08-17 15:08:11 发布

二叉搜索树是二叉树中最具实用价值的一种——"有序"赋予了它二分查找的能力，却也带来了验证的陷阱。本文从 BST 基础定义出发，通过 LeetCode 98 验证二叉搜索树（Medium）和 235 二叉搜索树的最近公共祖先（Easy）两道经典题，深入理解 BST 的"有序性"如何在解题中发挥作用。附三语言代码（Python / Java / C++）、mermaid 流程图，以及 BST 家族题扩展（700 搜索、701 插入、450 删除、230 第K小元素）。

引言：BST——二叉树中最"有序"的一种

在二叉树的世界里，大多数树都是"结构"意义上的树——它们只关心谁左谁右，不关心值的大小。但**二叉搜索树（BST）**不一样，它在结构的基础上，给每个节点的值加上了严格的约束。

这个约束看似简单——"左小右大"——但它带来的改变是革命性的：

普通二叉树：查找一个元素，最坏情况要遍历整棵树 O(n)
二叉搜索树：查找一个元素，利用二分思想，只需 O(h) 时间（h 为树高）

这就是"有序"的力量。

🤔 思考：既然 BST 查找这么快，为什么实际开发中我们不用 BST 做搜索，而是用哈希表？因为 BST 的查找效率依赖于树的高度——当树退化成链表时，BST 的查找就变成了 O(n)。这也是为什么平衡树（AVL、红黑树）如此重要。

但"有序"既是优势，也是陷阱。不是所有看起来"左<根<右"的树都是 BST——这就是我们今天的第一个重点：如何验证一棵树是 BST？

本期我们就用两道经典题——98 验证二叉搜索树（Medium）和 235 二叉搜索树的最近公共祖先（Easy）——把 BST 的有序性彻底搞懂。

BST 基础

什么是 BST？

二叉搜索树（Binary Search Tree，BST）是一棵满足以下性质的二叉树：

左子树所有节点的值 < 根节点的值
右子树所有节点的值 > 根节点的值
左右子树也分别是 BST

⚠️ 关键：这是"全局"定义，不是"局部"定义。左子树中所有节点都必须小于根节点，不仅仅是左子节点。

BST 与普通二叉树的区别

维度	普通二叉树	二叉搜索树
节点值约束	无	左<根<右（全局）
查找效率	O(n)	O(h)
中序遍历	无序	严格递增
适用场景	通用树结构	有序数据、快速查找

中序遍历有序性

BST 最重要的性质之一：中序遍历 BST 得到的是一个严格递增的序列。

中序遍历：左子树 → 根节点 → 右子树
BST 保证：左子树值 < 根 < 右子树值
因此遍历结果：严格递增

这个性质直接用于解决 98 验证 BST 的问题——只要中序遍历结果不是递增的，就不是 BST。

BST 结构图

🤔 思考：上图中，中序遍历结果是 1, 3, 4, 6, 7, 8, 10, 13, 14——严格递增。如果有一棵树的局部看起来是"左<根<右"，但中序遍历不是递增的，那它就不是 BST。这就是验证 BST 的核心思路。

BST 的常见操作复杂度

操作	平均	最坏（退化为链表）
查找	O(h)	O(n)
插入	O(h)	O(n)
删除	O(h)	O(n)

其中 h 为树高，平衡 BST 中 h = O(log n)，不平衡 BST 中 h = O(n)。

98 验证二叉搜索树（Medium）

题目描述

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

有效 BST 定义如下：

节点的左子树只包含小于当前节点的数

节点的右子树只包含大于当前节点的数

所有左子树和右子树自身必须也是二叉搜索树

示例：

输入：root = [2, 1, 3]
输出：true
解释：
    2
   / \
  1   3
1 < 2 < 3 ✓

输入：root = [5, 1, 4, null, null, 3, 6]
输出：false
解释：
    5
   / \
  1   4
     / \
    3   6
局部看 4 < 5, 3 < 4 < 6 都成立
但全局看 3 在 5 的右子树中，3 < 5 不成立 ✗

陷阱示例分析

第二个例子是 BST 验证中最经典的陷阱。只看每个节点的局部关系：

5 的左子节点 1 < 5 ✓
5 的右子节点 4 > 5 ✓
4 的左子节点 3 < 4 ✓
4 的右子节点 6 > 4 ✓

每个节点都满足"左<根<右"，但这不是 BST！因为 3 在 5 的右子树中，却小于 5。

🤔 思考：这就是为什么"只检查左<根<右"是不够的。BST 的验证要求全局约束——右子树中所有节点都必须大于根节点，不仅仅是右子节点。所以我们需要一种方法，在递归遍历时"传递"每个节点的合法取值范围。

解法一：中序遍历法

思路：利用 BST 中序遍历得到严格递增序列的性质。中序遍历过程中，维护一个"前驱节点"变量，检查当前节点值是否大于前驱节点值。

关键点：前驱节点的初始值需要设为负无穷（或 None），因为 BST 中第一个节点没有前驱。

三语言代码

# Python 中序遍历法
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 前驱节点值，初始化为负无穷
        self.prev = float('-inf')

        def inorder(node):
            if not node:
                return True
            # 检查左子树
            if not inorder(node.left):
                return False
            # 检查当前节点是否大于前驱
            if node.val <= self.prev:
                return False
            # 更新前驱
            self.prev = node.val
            # 检查右子树
            return inorder(node.right)

        return inorder(root)

// Java 中序遍历法
class Solution {
    private long prev = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return true;
        // 检查左子树
        if (!inorder(node.left)) return false;
        // 检查当前节点是否大于前驱
        if (node.val <= prev) return false;
        // 更新前驱
        prev = node.val;
        // 检查右子树
        return inorder(node.right);
    }
}

// C++ 中序遍历法
class Solution {
private:
    long long prev = LLONG_MIN;

    bool inorder(TreeNode* node) {
        if (!node) return true;
        // 检查左子树
        if (!inorder(node->left)) return false;
        // 检查当前节点是否大于前驱
        if (node->val <= prev) return false;
        // 更新前驱
        prev = node->val;
        // 检查右子树
        return inorder(node->right);
    }

public:
    bool isValidBST(TreeNode* root) {
        return inorder(root);
    }
};

解法二：递归区间法（核心解法）

思路：每个节点都有一个合法的取值范围区间 (min, max)。递归遍历时，将当前节点的合法区间传递给子节点。

根节点：合法区间为 (-∞, +∞)
左子节点：合法区间为 (min, root.val)
右子节点：合法区间为 (root.val, max)

为什么用 Long 而不是 Integer？ 因为节点值可能为 Integer.MIN_VALUE 或 Integer.MAX_VALUE，如果用 int 作为上下界边界值，边界情况会出错。

递归区间法工作过程图

🤔 思考：递归区间法的本质是什么？它把"全局约束"转化为"局部区间检查"。每个节点只需要检查自己是否在合法区间内，而这个区间是由祖先节点传递下来的。这样，全局约束就被分解成了一个个局部检查，递归地完成验证。

三语言代码

# Python 递归区间法
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True
            # 检查当前节点是否在合法区间内
            if node.val <= min_val or node.val >= max_val:
                return False
            # 递归检查左右子树，更新区间
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))

        return validate(root, float('-inf'), float('inf'))

// Java 递归区间法
class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

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

// C++ 递归区间法
class Solution {
private:
    bool validate(TreeNode* node, long long min, long long max) {
        if (!node) return true;
        // 检查当前节点是否在合法区间内
        if (node->val <= min || node->val >= max) return false;
        // 递归检查左右子树，更新区间
        return validate(node->left, min, node->val) &&
               validate(node->right, node->val, max);
    }

public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LLONG_MIN, LLONG_MAX);
    }
};

两种解法对比

维度	中序遍历法	递归区间法
核心思想	利用中序遍历有序性	传递合法区间约束
代码量	稍多（需要维护前驱变量）	更简洁
空间复杂度	O(n)	O(n)
理解难度	直观（中序遍历+递增检查）	抽象（区间传递）
面试推荐	可作为补充方案	✅ 推荐，更体现 BST 本质

易错点总结

只检查左<根<右是不够的：必须维护全局上下界
前驱节点初始值：中序遍历法中，前驱节点初始值设为负无穷，不能用 0 或其他固定值
节点值可能为 Integer.MIN_VALUE：上下界要用更大的类型（Long / float('inf')）
严格递增 vs 非严格递增：BST 要求严格递增，node.val <= prev 就返回 false
空树是 BST：空树满足 BST 定义

复杂度分析

时间复杂度：O(n)，每个节点恰好访问一次
空间复杂度：O(n)，最坏情况下递归栈深度为 n（树退化为链表）

235 二叉搜索树的最近公共祖先（Easy）

题目描述

给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。

最近公共祖先（LCA）定义为：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

示例：

输入：root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
输出：6
解释：节点 2 和节点 8 的最近公共祖先是 6

输入：root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
输出：2
解释：节点 2 和节点 4 的最近公共祖先是 2（一个节点可以是自己的祖先）

与 236 普通二叉树 LCA 的区别

这个问题有一个前身——236 二叉树的最近公共祖先（普通二叉树）。两者的核心区别在于：

维度	236 普通二叉树 LCA	235 BST 的 LCA
有序性	无	有（左<根<右）
解法思路	后序遍历，自底向上	利用有序性，自顶向下
时间复杂度	O(n)	O(h)
空间复杂度	O(n)	O(h) 或 O(1)
代码复杂度	较复杂	更简洁

🤔 思考：为什么 BST 的 LCA 更简单？因为 BST 的有序性告诉我们"方向"——如果 p 和 q 都在 root 左边，那 LCA 不可能在右边；如果 p 和 q 在 root 两侧，那 root 就是 LCA。而普通二叉树没有这个信息，只能遍历整棵树。

利用 BST 特性

BST 的有序性让 LCA 问题变得异常简单：

如果 p.val < root.val < q.val（或反之）：p 和 q 在 root 两侧，root 就是 LCA
如果 p.val < root.val 且 q.val < root.val：p 和 q 都在左子树，LCA 在左子树
如果 p.val > root.val 且 q.val > root.val：p 和 q 都在右子树，LCA 在右子树
如果 p.val == root.val 或 q.val == root.val：root 就是 LCA（一个节点可以是自己的祖先）

解法一：递归法

思路：根据 p、q 与 root 的大小关系，决定向哪个方向搜索。

三语言代码

# Python 递归法
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # p 和 q 都在左子树
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        # p 和 q 都在右子树
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        # p 和 q 在 root 两侧，或 p/q 等于 root，root 就是 LCA
        return root

// Java 递归法
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // p 和 q 都在左子树
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // p 和 q 都在右子树
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        // p 和 q 在 root 两侧，或 p/q 等于 root
        return root;
    }
}

// C++ 递归法
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // p 和 q 都在左子树
        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        // p 和 q 都在右子树
        if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        // p 和 q 在 root 两侧，或 p/q 等于 root
        return root;
    }
};

解法二：迭代法

思路：用 while 循环代替递归，根据大小关系移动当前节点。比递归更简洁，且空间复杂度 O(1)。

三语言代码

# Python 迭代法
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root
        while cur:
            if p.val < cur.val and q.val < cur.val:
                cur = cur.left
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                # p 和 q 在 cur 两侧，或 p/q 等于 cur
                return cur
        return None  # 题目保证 p、q 存在，不会执行到这里

// Java 迭代法
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (cur != null) {
            if (p.val < cur.val && q.val < cur.val) {
                cur = cur.left;
            } else if (p.val > cur.val && q.val > cur.val) {
                cur = cur.right;
            } else {
                // p 和 q 在 cur 两侧，或 p/q 等于 cur
                return cur;
            }
        }
        return null;
    }
}

// C++ 迭代法
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        while (cur) {
            if (p->val < cur->val && q->val < cur->val) {
                cur = cur->left;
            } else if (p->val > cur->val && q->val > cur->val) {
                cur = cur->right;
            } else {
                // p 和 q 在 cur 两侧，或 p/q 等于 cur
                return cur;
            }
        }
        return nullptr;
    }
};

复杂度分析

解法	时间复杂度	空间复杂度
递归法	O(h)	O(h)（递归栈）
迭代法	O(h)	O(1)

其中 h 为树高。在平衡 BST 中 h = O(log n)，退化为链表时 h = O(n)。

与 236 普通二叉树 LCA 的对比

# 236 普通二叉树 LCA 的后序遍历解法（用于对比）
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    return left or right

236 的解法特点：

必须遍历整棵树（后序遍历）
自底向上，从叶子节点逐层返回结果
如果 left 和 right 都非空，说明 p、q 分别在 root 两侧，root 就是 LCA
时间复杂度 O(n)，空间复杂度 O(n)

235 的解法特点：

利用有序性，自顶向下搜索
不需要遍历整棵树，只需沿一条路径走到底
时间复杂度 O(h)，迭代法空间 O(1)

🤔 思考：如果你已经掌握了 236 的解，学 235 时最重要的是转变思维——从"自底向上"变成"自顶向下"。普通二叉树没有有序性，只能从下往上找；BST 有了有序性，就可以从上往下判断方向。这种思维转变，比背代码重要得多。

BST 家族题

BST 的题目远不止 98 和 235，下面这些题都是 BST 的经典应用，可以用我们学到的 BST 有序性来解。

家族题一览表

题目	难度	核心思路	与本文关系
700 二叉搜索树中的搜索	Easy	利用 BST 有序性二分查找	最基本的 BST 操作
701 二叉搜索树中的插入操作	Medium	根据大小关系找插入位置	BST 插入标准写法
450 删除二叉搜索树中的节点	Medium	分类讨论（叶/单子/双子）	BST 最复杂的操作
230 二叉搜索树中第K小的元素	Medium	中序遍历第 K 个	中序遍历有序性应用

700 二叉搜索树中的搜索

给定一棵 BST 和一个值 val，返回值为 val 的节点，不存在则返回 null。

一句话思路：利用 BST 有序性，像二分查找一样搜索——val < root.val 去左子树，val > root.val 去右子树，相等则返回。

701 二叉搜索树中的插入操作

向 BST 中插入一个值，保证插入后仍然是 BST。

一句话思路：根据大小关系找到插入位置（递归或迭代），在叶子节点处插入新节点。

450 删除二叉搜索树中的节点

从 BST 中删除一个值，保证删除后仍然是 BST。

一句话思路：分三种情况讨论——（1）叶子节点：直接删除；（2）只有一个子节点：用子节点替代；（3）有两个子节点：找到右子树的最小节点（后继）或左子树的最大节点（前驱）替代当前节点，然后递归删除替代节点。

230 二叉搜索树中第K小的元素

找到 BST 中第 K 小的元素。

一句话思路：BST 中序遍历得到递增序列，中序遍历到第 K 个元素就是答案。

对比总结

今天的两道题从不同角度利用了 BST 的"有序性"：

维度	98 验证 BST	235 BST 的 LCA
与有序性的关系	验证有序性	利用有序性
核心思路	中序遍历递增 / 区间约束	大小关系决定搜索方向
操作方向	自底向上（中序遍历）或自顶向下（递归区间）	自顶向下
对应普通二叉树题	无（普通二叉树不需要验证 BST）	236 二叉树的 LCA