验证二叉搜索树

2025/10/16

思路：递归定义，所以递归遍历

手写代码：

def isValidBST(root, ):
    if root.left is None and root.right is None:
        return True
    if root.left:
        if root.left >= root.val:
            return false
    if root.right:
        if root.right <= root.val:
            return false

    return isValidBST(root.left) and isValidBST(root.right)

评价：只比较了局部的左右孩子，没有比较全部的

重新手写代码：

def isValidBST(root, minval=-inf, maxval=inf):
    left_maxval = min(root.val, maxval)
    right_minval = max(root.val, minval)
    if root.left is None and root.right is None:
        return True
    if root.left:
        if root.left >=left_maxval:
            return false
    if root.right:
        if root.right <= right_minval:
            return false

    return isValidBST(root.left, maxval=left_maxval) and isValidBST(root.right, minval=right_minval)

isValidBST(root, minval=-inf, maxval=inf)

评价：完全正确