二叉搜索树（BST）的验证

题目描述
给定一个二叉树的根节点，判断该二叉树是否是一个有效的二叉搜索树（BST）。有效的BST需满足：

1. 节点的左子树只包含小于当前节点的数；
2. 节点的右子树只包含大于当前节点的数；
3. 所有左子树和右子树自身也必须是BST。

解题思路

1. 理解BST的定义
   BST的中序遍历结果是一个严格递增序列。利用这一性质，可以通过中序遍历验证节点值是否递增。

2. 递归法（利用上下界）

   • 遍历每个节点时，记录其允许的取值范围（最小值和最大值）。
   • 初始时根节点的范围为(-∞, +∞)。
   • 左子节点的上限为当前节点值，下限继承父节点的下限。
   • 右子节点的下限为当前节点值，上限继承父节点的上限。

3. 中序遍历法

   • 中序遍历二叉树，检查每个节点值是否大于前一个节点值。
   • 使用全局变量记录前一个节点的值，初始化为-∞。

逐步详解

方法一：递归上下界法

def isValidBST(root):
    def check(node, min_val, max_val):
        if not node:
            return True
        # 当前节点值必须在(min_val, max_val)开区间内
        if node.val <= min_val or node.val >= max_val:
            return False
        # 递归检查左子树和右子树，更新上下界
        return (check(node.left, min_val, node.val) and 
                check(node.right, node.val, max_val))
    
    return check(root, float('-inf'), float('inf'))

步骤解析：

1. 从根节点开始，初始上下界为负无穷和正无穷。
2. 检查当前节点值是否在范围内，若越界则返回False。
3. 递归左子树时，将当前节点值作为新上界（左子节点值需小于父节点）。
4. 递归右子树时，将当前节点值作为新下界（右子节点值需大于父节点）。

方法二：中序遍历法

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)

步骤解析：

1. 中序遍历顺序：左子树 → 当前节点 → 右子树。
2. 遍历过程中记录前一个节点的值prev。
3. 若当前节点值不大于prev，说明不满足递增顺序，返回False。
4. 遍历完整棵树若无违规，则为有效BST。

复杂度分析

• 时间复杂度：O(N)，每个节点被访问一次。
• 空间复杂度：O(N)，递归栈的深度在最坏情况（链状树）下为N。

边界案例

• 空树是有效的BST。
• 单节点树是有效的BST。
• 包含重复值的树无效（需严格大于/小于）。

总结
两种方法均能高效验证BST。递归法直观体现BST定义，中序遍历法利用有序性简化检查。实际面试中可先阐述思路，再选择一种实现，并注意处理整数边界（如使用None代替无穷大）。