验证二叉搜索树

维杰 - 拉贾:

给定一个二叉树,确定它是否是一个有效的二叉搜索树(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条件?即使没有他们,职能应该从下面右侧的,如果条件返回false?我缺少的是在这里吗?

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

你基本上是问有什么区别之间:

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调用和行为适当,返回false如果子树不是BST。第二检查子树,然后返回true不管。


这个很重要。一个有效的BST的定义是,root大于root.left和小于root.right,并且这两个root.leftroot.right有效BSTS。

通过忽略那些返回值,你检查的唯一事情是一个有效的BST,顶部三个节点。换句话说,这将传递虽然是无处附近有效:

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

如果没有在返回结果每一个递归的层次,你基本上失去它。

考虑下面的代码,这是类似于你在评论提出的问题(“但是辅助函数里面,有一个条件,如果它返回false右那如何不来这里发挥作用?”):

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

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

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

这版画None,因为,即使你返回42两个级别,这是扔掉的水平之一。

正确的方法将改变level2()呼叫进入return level2()


顺便说一句,我不知道珍惜您取得upperlower在这里。

的有效性是指递归定义的唯一你需要检查的就是三个直接节点和子树。

换句话说,这就够了(伪代码,即使它看起来像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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章