验证二进制搜索树

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的前三个节点。换句话说，尽管无处
near有效：
    __1__
   /     \
  2       3
 / \     / \
9   9   9   9
没有在
every
级别上返回结果，基本上就失去了它。考虑一下代码，该代码类似于您在注释中提出的问题（“但是在辅助函数中，有一个if条件返回假权限？这在这里不起作用吗？”）：

---

def level2():
    return 42
def level1():
    level2()
print(level1())

这将打印None，因为即使您在第二级返回42，也将在第一级被丢弃。正确的方法会将level2()调用更改为return level2()。