验证二叉搜索树代码错误排查：输入[5,1,4,null,null,3,6]输出不符

问题描述 #

在LeetCode「验证二叉搜索树」题目中，输入树节点数组[5,1,4,null,null,3,6]时，代码输出结果为True，但预期输出应为False。

用户代码 #

# 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 lcheck(rt,c,rb4,rflux=None): #rb4=ROOT BEFORE,# rflux=root after which the direction changed
#C=0 Means the outermost branch of the tree                                                                     
            if rt:
                if c==0:
                    if rt.val>=rb4.val:
                        return False
                    lcheck(rt.left,0,rt,rflux=None)
                    rcheck(rt.right,1,rt,rb4)
                if c==1:
                    if rt.val>=rb4.val or rt.val<= rflux.val:
                        return False
                    lcheck(rt.left,1,rt,rflux)
                    rcheck(rt.right,1,rt,rb4)
        def rcheck(rt,c,rb4,rflux=None):
            if rt:
                if c==0:
                    if rt.val<=rb4.val:
                        return False
                    lcheck(rt.left,1,rt,rflux=rb4)
                    rcheck(rt.right,0,rt,rflux=None)
                if c==1:
                    if rt.val<=rb4.val or rt.val>= rflux.val:
                        return False
                    lcheck(rt.left,1,rt,rb4)
                    rcheck(rt.right,1,rt,rflux)
        lcheck(root.left,0,root)
        rcheck(root.right,0,root) 
        return True

错误原因分析 #

1. 递归调用未传递返回结果 #

lcheck和rcheck函数在递归调用子节点时，没有接收并向上传递递归的返回值。比如当某个子节点检查发现不符合条件返回False时，上层函数完全忽略这个结果，继续执行后续代码，最终导致错误的结果被掩盖。

以示例中的情况为例：检查右子树的左节点3时，lcheck会触发rt.val<=rflux.val（3<=5）的条件，返回False，但这个返回值没有被上层的rcheck接收处理，上层函数继续执行，没有把False传递到最外层。

2. 函数缺少明确的返回值 #

• 当节点为空时，没有返回True（空节点属于合法的二叉搜索树节点）。
• 当所有检查都通过时，函数也没有明确返回True，Python会默认返回None，而主函数没有判断这些递归的返回结果，直接返回True，完全忽略了检查过程的实际结果。

3. 主函数未处理检查结果 #

主函数中调用lcheck和rcheck后，没有判断这两个函数的返回值，直接返回True。就算检查过程中发现了不合法的节点，这个错误也不会被反馈到最终结果里。

修正思路 #

• 所有递归调用必须接收返回值，一旦发现返回False，立即向上返回False，终止后续检查。
• 当节点为空时，返回True。
• 每个检查分支完成后，若所有子节点检查都通过，返回True。
• 主函数需要判断lcheck和rcheck的返回值，只有两者都为True时才返回True。

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