我来给你讲解 LeetCode 第 98 题：验证二叉搜索树（Validate Binary Search Tree）。

题目描述

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

二叉搜索树的定义：

• 节点的左子树只包含小于当前节点的数
• 节点的右子树只包含大于当前节点的数
• 所有左子树和右子树自身也必须是二叉搜索树

示例：

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false（因为右子树中的节点3小于根节点5）

解题思路分析

第一步：理解BST的核心特性

二叉搜索树的关键特性是中序遍历的有序性。如果对BST进行中序遍历（左-根-右），得到的应该是一个严格递增的序列。

第二步：错误思路分析

很多人的第一想法是只检查当前节点与直接子节点的大小关系：

# 这是错误的！
def isValidBST(root):
    if not root:
        return True
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False
    return isValidBST(root.left) and isValidBST(root.right)

为什么错误？ 因为BST要求整个左子树的所有节点都小于当前节点，而不仅仅是直接左子节点。

第三步：正确解法1 - 中序遍历

思路：进行中序遍历，在遍历过程中检查当前节点值是否大于前一个节点值。

具体步骤：

1. 初始化一个变量记录前一个遍历的节点值（设为负无穷）
2. 进行中序遍历（递归或迭代）
3. 对于每个节点，检查是否大于前一个节点值
4. 如果违反递增规则，立即返回false

代码实现：

def isValidBST(root):
    prev = float('-inf')  # 记录前一个节点值
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        
        # 遍历左子树
        if not inorder(node.left):
            return False
        
        # 检查当前节点
        if node.val <= prev:
            return False
        prev = node.val  # 更新前一个节点值
        
        # 遍历右子树
        return inorder(node.right)
    
    return inorder(root)

时间复杂度：O(n)，空间复杂度：O(h)，h为树高

第四步：正确解法2 - 递归上下界法

思路：在递归过程中传递当前节点值的允许范围（最小值和最大值）。

具体步骤：

1. 从根节点开始，允许范围是(-∞, +∞)
2. 对于左子节点，允许范围是(当前最小值, 父节点值)
3. 对于右子节点，允许范围是(父节点值, 当前最大值)
4. 如果节点值不在允许范围内，返回false

代码实现：

def isValidBST(root):
    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'))

第五步：两种方法的比较

中序遍历法：

• 优点：思路直观，代码简洁
• 缺点：需要遍历整个树才能确定结果

上下界法：

• 优点：可以在发现无效节点时立即返回，效率可能更高
• 缺点：边界条件需要仔细处理

第六步：边界情况处理

需要特别注意的边界情况：

1. 空树是有效的BST
2. 单节点树是有效的BST
3. 节点值可能等于边界值（要用严格不等号）
4. 节点值可能是整数的最小/最大值

第七步：总结

验证BST的核心是理解中序遍历的有序性和子树值的范围约束。两种方法都体现了BST的本质特性，在实际应用中可以根据具体情况选择合适的方法。

这个题目很好地考察了对二叉树遍历和BST性质的理解，是学习树结构的重要基础题目。