我来给你讲解 LeetCode 第 98 题「验证二叉搜索树」。

题目描述

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

二叉搜索树的定义：

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

示例：

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

输入：root = [5,1,4,null,null,3,6]
输出：false

解题思路分析

第一步：理解二叉搜索树的本质

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

第二步：基础思路 - 中序遍历验证

最直观的方法是：

1. 进行中序遍历，将节点值存入数组
2. 检查数组是否严格递增

def isValidBST(root):
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    values = inorder(root)
    for i in range(1, len(values)):
        if values[i] <= values[i-1]:
            return False
    return True

时间复杂度：O(n)，需要遍历所有节点
空间复杂度：O(n)，需要存储所有节点值

第三步：优化空间复杂度 - 递归中直接判断

我们可以在中序遍历的过程中直接判断是否有序，不需要存储整个遍历结果。

关键思路：维护一个变量记录前一个节点的值，在遍历过程中比较当前节点值是否大于前一个节点值。

def isValidBST(root):
    prev = None  # 记录前一个节点的值
    
    def inorder(node):
        nonlocal prev
        if not node:
            return True
        
        # 遍历左子树
        if not inorder(node.left):
            return False
        
        # 检查当前节点
        if prev is not None and node.val <= prev:
            return False
        prev = node.val
        
        # 遍历右子树
        return inorder(node.right)
    
    return inorder(root)

工作原理：

1. 按照左-根-右的顺序遍历
2. 每次处理当前节点时，检查是否大于前一个节点值
3. 如果发现违反规则，立即返回False

第四步：另一种思路 - 上下界约束法

更符合BST定义的思路：每个节点都有一个合法的值范围。

递归思路：

• 根节点的范围是(-∞, +∞)
• 左子节点的范围是(min, 父节点值)
• 右子节点的范围是(父节点值, max)

def isValidBST(root):
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        # 检查当前节点值是否在合法范围内
        if min_val is not None and node.val <= min_val:
            return False
        if max_val is not None and 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, None, None)

举例说明：

    5
   / \
  1   7
     / \
    3   9

• 节点5：范围(-∞, +∞)，合法
• 节点1：范围(-∞, 5)，合法
• 节点7：范围(5, +∞)，合法
• 节点3：范围(5, 7)，但3<5，非法！

第五步：迭代解法（栈模拟中序遍历）

对于不喜欢递归的同学，可以用迭代方式实现中序遍历验证：

def isValidBST(root):
    stack = []
    prev = None
    curr = root
    
    while curr or stack:
        # 遍历到最左节点
        while curr:
            stack.append(curr)
            curr = curr.left
        
        curr = stack.pop()
        
        # 检查顺序
        if prev is not None and curr.val <= prev:
            return False
        prev = curr.val
        
        # 转向右子树
        curr = curr.right
    
    return True

关键要点总结

1. 核心思想：利用BST的中序遍历有序性
2. 边界情况：空树是有效的BST；节点值可能等于INT_MIN或INT_MAX
3. 易错点：不能只检查每个节点与其直接子节点的关系，必须保证整个子树都在正确范围内
4. 推荐解法：上下界约束法最符合BST定义，且易于理解

通过以上循序渐进的分析，你应该能够深入理解如何验证二叉搜索树了！