对 'Validate Binary Search Tree' 问题的预期输出感到困惑

Question

我正在尝试编写一种算法来验证二叉搜索树。这是为了回答以下算法问题：https://leetcode.com/problems/validate-binary-search-tree/。我选择使用递归方法并在 Python3:

中编写了以下代码

def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        left = self.isValidBST(root.left)
        right = self.isValidBST(root.right)
        if left and right:
            if (root.left and root.val <= root.left.val) or (root.right and root.val >= root.right.val):
                return False
            return True
        return False

以上算法运行到leetcode平台提供的第71个测试用例。但是，它在以下输入时失败：

[5,4,6,null,null,3,7]

预期输出为 False（即不是二叉搜索树）。但是，我的算法输出 True。我已经多次查阅问题描述和提供的图表，我相信我的输出是正确的。考虑到这一点，有什么我想念的吗？还是平台不对？

Answer 1

输入 [5,4,6,null,null,3,7] 具有以下树表示。

这显然不是一个有效的二叉搜索树，因为节点 3 小于它的大节点 parent 5.

在二叉搜索树中，右侧的每个 节点（包括所有祖先节点）必须大于（或大于或等于，具体取决于您的定义）。左子树也是如此。请注意，这种情况下的 leetcode 问题明确指出它们必须 less 和 greater 所以 equal无效。这样想：您需要能够在 BST 中进行二进制搜索。当您向右走时，您希望那里的所有节点都大于 parent。如果在那里找到小于 parent 的节点，则排序被破坏并且您无法进行二进制搜索。您需要线性搜索。在这个例子中二进制搜索 3 会 return false，虽然它显然在那里。所以，它不是一个有效的二叉搜索树。

您的算法只检查直接的左右 children 是否遵守此条件。

要更正它，您需要将允许的最小值和最大值传递给递归函数。当您向左走时，您将最大值设置为等于当前节点值。当您向右走时，将最小值设置为当前节点值。这确保了，假设节点左侧的节点永远不会大于该节点。

一种可能的实现方式如下：

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.isValidBSTHelper(root, None, None)
    def isValidBSTHelper(self, root: TreeNode, min_val: int, max_val: int)-> bool:
        if root == None: return True
        if (min_val != None and root.val <= min_val) or (max_val != None and root.val >= max_val):
            return False
        
        return self.isValidBSTHelper(root.left, min_val, root.val) \
                and self.isValidBSTHelper(root.right, root.val, max_val)

对 'Validate Binary Search Tree' 问题的预期输出感到困惑

Confused about expected output for a 'Validate Binary Search Tree' question

algorithm

tree

binary-tree

binary-search-tree

data-structures