验证二叉搜索树

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

- user11138349

---

你对 helper() 的两个调用没有任何作用。它们为什么在那里？ - quamrana

也许将 helper 重命名为 is_subtree_within_bounds 可以帮助理解正在发生的事情。 - rdas

@quamrana 如果不在范围内，它们不会返回false吗？ - user11138349

当帮助函数调用自身并返回 False，它并不会退出调用它的帮助函数。这就是函数调用的工作方式，也是递归的工作方式。 - quamrana

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

---

如果不在每个递归层级中返回结果，你基本上就会失去它。

考虑下面的代码，类似于你在评论中提出的问题（“但是在辅助函数内部，有一个返回false的if条件语句，为什么这里没有起作用？”）：

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

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

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

由于即使在第二层返回42，它在第一层被丢弃，因此这将打印出None。

正确的方法是将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

- paxdiablo

---

但是在辅助函数内部，有一个if条件语句返回false，这个怎么不适用于这里呢？ - user11138349