使用DFS验证二叉搜索树(BST)的代码错误排查与解法

错误原因 #

你当前的代码逻辑存在核心缺陷：仅校验了当前节点与直接左右子节点的大小关系，没有考虑上层祖先节点对当前子树所有节点的全局约束。BST的规则要求某节点的左子树所有节点都小于该节点、右子树所有节点都大于该节点，而不是仅要求直接子节点满足条件。

你提到的两个测试用例错误原因完全一致：

• 用例[5,1,4,null,null,3,6]中，节点3处于根节点5的右子树，按照规则必须大于5，但你的代码仅校验了它小于父节点4，漏了全局约束校验
• 用例[5,4,6,null,null,3,7]中，节点3同样处于根节点5的右子树，合法值需要大于5，你的代码未校验该层约束导致误判

错误代码走查（以[5,1,4,null,null,3,6]为例） #

你的代码执行流程如下：

1. 校验根节点5：左子节点1 < 5，右子节点4 >5，符合直接子节点校验，递归左右子树
2. 校验左子树1：无左右子节点，返回True
3. 校验右子树4：左子节点3 <4，右子节点6>4，符合直接子节点校验，递归左右子树
4. 校验3、6节点：无左右子节点，均返回True
5. 最终代码返回True，和预期结果False不符

正确解题思路 #

采用带上下界约束的DFS遍历：每个节点在遍历时都携带合法的取值范围(low, high)，节点值必须严格落在这个区间内才合法。

• 根节点无祖先约束，初始区间为(-inf, +inf)
• 遍历当前节点的左子节点时，左子节点的上界更新为当前节点的值，下界继承当前节点的下界（左子树所有节点必须小于当前节点，同时要满足上层祖先的下界要求）
• 遍历当前节点的右子节点时，右子节点的下界更新为当前节点的值，上界继承当前节点的上界（右子树所有节点必须大于当前节点，同时要满足上层祖先的上界要求）

正确代码实现 #

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node, low=float('-inf'), high=float('inf')):
            if not node:
                return True
            # 当前节点值不在合法区间内直接返回False
            if not (low < node.val < high):
                return False
            # 递归校验左右子树，同步更新对应上下界
            return dfs(node.left, low, node.val) and dfs(node.right, node.val, high)
        
        return dfs(root)

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