LeetCode 98.验证二叉搜索树 前序遍历代码错误排查

我正在研究LeetCode题目 98. Validate Binary Search Tree（验证二叉搜索树）：

给定二叉树的根节点root，判断其是否为有效的二叉搜索树（BST）。

有效BST的定义如下：

• 节点的左子树仅包含键值小于该节点键值的节点。
• 节点的右子树仅包含键值大于该节点键值的节点。
• 所有左、右子树本身也必须是二叉搜索树。

现有如下使用前序遍历校验二叉树性质的代码，运行不符合预期：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def preorder(root):
        
            if root.left!=None:
                if root.left < root.val:
                    preorder(root.left)
                else:
                    return False
            
        
            if root.right!=None:
                if root.right>root.val:
                    preorder(root.right)
                else:
                    return False
       
    t= preorder(root)
    return t!=False

该代码在测试用例root=[2,1,3]上返回了False，和预期结果不符。

代码存在的具体问题 #

这段代码从语法到逻辑一共有5处错误，直接导致运行异常：

• 取值错误：root.left、root.right是TreeNode类型的对象，不是节点存储的数值，直接和整数root.val做大小比较本身就不符合逻辑，正确取值应该是root.left.val、root.right.val。
• 递归返回值丢失：调用preorder(root.left)、preorder(root.right)做子树校验时，没有接收递归返回的结果。就算子树遍历发现不符合BST规则返回了False，上层递归也拿不到这个结果，不会及时终止返回错误。
• 缺少合法分支的返回值：当节点是叶子节点（左右子节点都为空），或者左右子树都校验通过时，preorder函数没有写返回True的逻辑，函数默认返回None。
• 缩进语法错误：t= preorder(root)和return t!=False两行的缩进层级不对，没有写在isValidBST方法的代码块内，方法执行时根本不会运行这两行逻辑。
• 校验逻辑有漏洞：就算修复所有语法问题，现有逻辑只比较了当前节点和直接左右子节点的大小，没有给子树传递上下界约束。比如根节点值为5、右子节点值为6、右子节点的左子节点值为4的场景，现有代码会误判为合法BST，实际上4小于根节点5，不符合BST规则。

修正后的前序遍历实现 #

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def preorder(node, min_val=float('-inf'), max_val=float('inf')):
            # 空节点默认合法
            if not node:
                return True
            # 当前节点值不在合法区间内直接返回False
            if not (min_val < node.val < max_val):
                return False
            # 递归校验左子树：上界更新为当前节点值，下界继承
            # 递归校验右子树：下界更新为当前节点值，上界继承
            return preorder(node.left, min_val, node.val) and preorder(node.right, node.val, max_val)
        
        return preorder(root)

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