函数来确定树是否是有效的BST？

Question

我必须确定是否给定一个代表树的列表，该树是否是有效的BST（这个问题来自leetcode）。我也看到了其他的帖子，但我想知道是否有人可以帮助我的方法，因为这显然是不正确的。例如，对于树[1,2,3]，其中1是根，2是左子项，3是右子项，我的代码返回true。希望它只需要一些小的更改，但可能整个函数的方法是不正确的。在

这是我的代码：

def isValidBST(self, root):
    if (root == None):
        return True
    if (root.left == None or root.left.val < root.val):
        return self.isValidBST(root.left)
    if (root.right == None or root.right.val > root.val):
        return self.isValidBST(root.right)
    return False

第二，我看到了一些方法，它使用了一个helper函数，它接受最小/最大值，但这让我很困惑。如果有人想解释为什么这种方法是一种好的/更好的方法，我们将不胜感激！在

Answer 1

以下是实现有效性检查的一种方法：

class BST:

    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def isValidBST(self):
        '''
        Simultaneously check for validity and set our own min and max values.
        '''
        self.min = self.max = self.value
        if self.left:
            if not self.left.isValidBST():
                return False
            if self.left.max >= self.value:
                return False
            self.min = self.left.min
        if self.right:
            if not self.right.isValidBST():
                return False
            if self.right.min < self.value:
                return False
            self.max = self.right.max
        return True

assert BST(2, BST(1), BST(3)).isValidBST()
case = BST(2, BST(1, None, BST(3)))
assert case.left.isValidBST()
assert not case.isValidBST()

Answer 2

我将为Nodes创建一个min_max方法，它可以找到根在Node上的树的最小值和最大值。在找到它们的同时进行健全性检查，然后isValidBST就可以捕捉到异常

def max_min(self): 

    '''
    Returns maximum and minimum values of the keys of the tree rooted at self. 
    Throws an exception if the results are not correct for a BST
    '''

    l_max, l_min = self.left.max_min() if self.left else (self.val, self.val)
    if l_max > self.val:
        raise ValueError('Not a BST')
    r_max, r_min = self.right.max_min() if self.right else (self.val, self.val)
    if r_min < self.val:
        raise ValueError('Not a BST')
    return l_min, r_max

def isValidBST(self):
    try:
        if self.max_min():
            return True
    except ValueError:
            return False