验证二叉搜索树

Question

给定一个二叉树，确定它是否是一个有效的二叉搜索树（BST）。

假设 BST 定义如下：

节点的左子树只包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true
Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

我的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            if not helper(node.right, node.val, upper):
                return False
            if not helper(node.left, lower, node.val):
                return False
            return True


        return helper(root)

上面的代码适用于所有测试用例。但是，下面的代码没有。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:



        def helper(node, lower = float('-inf'), upper = float('inf')):
            if(not node):
                return True

            if(node.val<=lower or node.val>=upper):
                return False
            helper(node.right, node.val, upper)
            helper(node.left, lower, node.val)
            return True


        return helper(root)

额外的 IF 条件需要什么？即使没有它们，函数也应该从下面的 if 条件返回 false 对吗？我在这里缺少什么？

 if(node.val<=lower or node.val>=upper):
                    return False

Answer 1

您基本上是在问以下之间有什么区别：

if not helper(node.right, node.val, upper):
    return False
if not helper(node.left, lower, node.val):
    return False
return True

和：

helper(node.right, node.val, upper)
helper(node.left, lower, node.val)
return True

第一个检查调用的返回值helper并进行适当的操作，如果子树不是 BST，则返回 false。第二个检查子树，然后无论如何都返回 true。

这个很重要。有效BST 的定义是root大于root.left且小于root.right，并且 和root.left也是root.right有效的 BST。

通过忽略这些返回值，您唯一要检查的是有效 BST 的前三个节点。换句话说，尽管远非有效，但这仍然会通过：

    __4__
   /     \
  2       8
 / \     / \
3   1   9   7

如果不返回每个递归级别的结果，您基本上就会丢失它。

考虑下面的代码，它类似于您在评论中提出的问题（“但是在辅助函数内部，有一个 if 条件返回 false，对吗？这里怎么不发挥作用？”）：

def level2():
    return 42          # Returns '42'.

def level1():
    level2()           # Returns 'None', not '42'.

print(level1())        # Prints 'None'.

这是None因为，即使您42在第二级返回，它也会在第一级被丢弃。

正确的方法是将调用更改level2()为return level2().

顺便说一句，我不确定您从这里获得什么upper价值lower。

有效性的递归定义意味着您唯一需要检查的是三个直接节点和子树。

换句话说，这就足够了（伪代码，尽管它看起来像 Python，后者是前者的理想基线）：

def isValidBst(node):
    # Empty tree is valid (or sub-tree, for that matter
    # but, since we never descend into a null, that's a
    # moot point).

    if node is null: return true

    # Check left value and sub-tree.

    if node.left is not null:
        if node.left.value >= node.value: return false
        if not isValidBst(node.left): return false

    # Check left value and sub-tree.

    if node.right is not null:
        if node.right.value <= node.value: return false
        if not isValidBst(node.right): return false

    # If there were no failures, including the possibility
    # we're at a leaf node, everything below this node is
    # okay.

    return true