LeetCode 98：验证二叉搜索树代码异常求助——为何判断错误？

问题根源 #

你的代码对二叉搜索树（BST）的核心规则理解有误。BST的正确规则是：

• 任意节点的左子树所有节点值都小于该节点值
• 任意节点的右子树所有节点值都大于该节点值
• 更关键的是：每个节点的取值必须处于动态范围内——比如根节点右分支的所有节点，不仅要大于根节点，还要满足所有祖先节点的下限要求；左分支节点则要满足所有祖先节点的上限要求。

你的代码存在两个致命问题：

1. 仅用当前父节点和根节点的值做判断，没有传递动态的上下限。比如输入里的节点3，它是6的左子节点，你的代码只验证了6>3且根节点5>3就认为合法，但实际上3处于根节点5的右分支，所有右分支节点必须大于5，3不满足这个条件。
2. 错误地用root.val作为所有子节点的统一判断标准，忽略了每个节点的子节点范围是继承自父节点的动态约束，而非固定和根节点对比。

输入用例的具体错误分析 #

输入用例的树结构：

5
   / \
  4   6
     / \
    3   7

当处理节点6的左子节点3时，你的代码判断：

• 6.val > 3.val（6>3，成立）
• root.val > 3.val（5>3，成立）
  因此将3加入队列，未返回False。但按照BST规则，3处于5的右分支，必须大于5，显然3不满足，你的代码漏掉了这个关键判断。

修复后的BFS版本代码 #

我们需要在BFS队列中存储每个节点的允许取值范围（下限、上限），子节点的范围由父节点的范围推导而来：

def isValidBST(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True
    # 队列存储(当前节点, 取值下限, 取值上限)
    queue = [(root, float('-inf'), float('inf'))]
    
    while queue:
        node, lower, upper = queue.pop(0)
        # 先检查当前节点是否在合法范围内
        if node.val <= lower or node.val >= upper:
            return False
        # 左子节点的上限是当前节点值，下限继承父节点的下限
        if node.left:
            queue.append((node.left, lower, node.val))
        # 右子节点的下限是当前节点值，上限继承父节点的上限
        if node.right:
            queue.append((node.right, node.val, upper))
    return True

代码说明 #

• 根节点初始范围是(-inf, +inf)，无父节点约束
• 左子节点的取值必须小于父节点值，同时大于父节点的下限
• 右子节点的取值必须大于父节点值，同时小于父节点的上限
• 每个节点先校验自身合法性，再处理子节点

用这个代码处理输入用例时，节点3的范围是(5,6)（继承自父节点6的范围(5, +inf)），而3<=5，会直接返回False，符合预期。

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