python - 检查树是否为二叉搜索树 (BST)

Question

我正在尝试解决一个二叉搜索树问题，但我无法通过所有测试用例。如果树是二叉搜索树，我需要返回 true，否则，我需要返回 false。谁能告诉我我做错了什么？

'''
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
'''

def checkBST(root):
    if root.left == None and root.right == None:
        return True
    if root == None:
        return True
    if root.left != None:
        if root.left.data < root.data:
            return True
    else:
        return False
    if root.right != None:
        if root.right.data > root.data:
            return True
        else:
            return False
    return chckBST(root.left) and chckBST(root) and chckBST(root.right)

Answer 1

你有很多多余的if代码中的条件。您可以像这样简化它:

def checkBST(root):
    if root == None or (root.left == None and root.right == None):
        return True

    elif root.right == None:
        return root.left.data < root.data and checkBST(root.left)

    elif root.left == None:
        return root.right.data >= root.data and checkBST(root.right)

    return checkBST(root.left) and checkBST(root.right)

首先，检查所有 None状况。 python 中的短路保证如果第一个条件是 False , 第二个不会被评估。这使您可以编写简洁的语句，例如 return root.left.data < root.data and checkBST(root.left) .

最后，在左节点和右节点都不为None的情况下, 不要调用checkBST(root)再次。这导致无限递归。