验证二叉搜索树（BST）的函数是否正确？能否优化？

一、函数有效性分析 #

你的这段验证BST的代码是有效的，核心逻辑完全契合二叉搜索树的定义：每个节点的值必须严格大于左子树的所有节点，严格小于右子树的所有节点。

通过递归传递上下界（mn为当前节点的最小允许值，mx为最大允许值）的方式，能精准约束每个节点的合法取值范围。你测试的有效树返回True，修改节点值（如把4改为5、7改为3）后返回False，也验证了逻辑的正确性。

不过存在一个边界漏洞：如果传入的root是None（空树），当前代码会直接抛出AttributeError，因为尝试访问root.val，而空树本身属于合法的二叉搜索树，需要补充处理。

二、优化方向与实现 #

1. 修复边界情况+简化递归逻辑 #

先处理空树的情况，同时简化左右子树的判断代码，让逻辑更紧凑：

class Node:
    val: int
    left: 'Node | None' = None
    right: 'Node | None' = None

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isValidBST(root: Node | None, mn=float('-Inf'), mx=float('+Inf')) -> bool:
    if not root:
        return True
    if not (mn < root.val < mx):
        return False
    # 合并左右子树的递归判断，只要有一个不合法就返回False
    return isValidBST(root.left, mn, root.val) and isValidBST(root.right, root.val, mx)

2. 迭代实现（避免递归栈溢出） #

如果树的高度极大（比如接近链表结构），递归会触发RecursionError，改用迭代的深度优先搜索（DFS）方式，用栈存储每个节点的上下界：

def isValidBST(root: Node | None) -> bool:
    if not root:
        return True
    # 栈中存储 (节点, 最小允许值, 最大允许值)
    stack = [(root, float('-Inf'), float('+Inf'))]
    while stack:
        node, mn, mx = stack.pop()
        if not (mn < node.val < mx):
            return False
        # 右子树先入栈（保证左子树先处理，和递归顺序一致）
        if node.right:
            stack.append((node.right, node.val, mx))
        if node.left:
            stack.append((node.left, mn, node.val))
    return True

3. 中序遍历验证（另一种思路） #

BST的中序遍历结果是严格递增的，也可以通过这个特性验证：

def isValidBST(root: Node | None) -> bool:
    prev = float('-Inf')
    stack = []
    current = root
    while stack or current:
        # 遍历到最左节点
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        if current.val <= prev:
            return False
        prev = current.val
        current = current.right
    return True

内容的提问来源于stack exchange，提问作者chocojunkie