递归验证二叉搜索树(BST)测试不通过 求代码错误排查

你的代码错误出在初始递归调用的参数传递上：
最后一行调用valid函数时，你给根节点传入的上界是float("-inf")（负无穷），正确的入参应该是float("inf")（正无穷）。

错误原因 #

BST根节点的取值没有上下限约束，合法范围是大于负无穷、小于正无穷。你给上下界都传了负无穷，导致根节点的校验条件node.val < right必然不成立，所有测试用例都会直接返回False，这就是你第一个测试用例[2,1,3]输出不符合预期的原因。

修正后代码 #

# 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 valid(node, left, right):
            if not node:
                return True
            
            if not (node.val>left and node.val<right):
                return False
            
            return (valid(node.left, left, node.val) and valid(node.right, node.val, right))
                    
        return valid(root, float("-inf"), float("inf"))

效果验证 #

修改后：

• 测试用例[2,1,3]：根节点2满足-∞ < 2 < +∞，左子节点1满足-∞ <1 <2，右子节点3满足2 <3 <+∞，返回True，符合预期。
• 测试用例[5,1,4,null,null,3,6]：右子节点4的校验范围是5 < 节点值 < +∞，4不满足大于5的条件，返回False，符合预期。

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