检查树是否是二进制搜索树(BST) [英] Check if a tree is a Binary Search Tree (BST)

问题描述

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

I am trying to solve a binary search tree problem, but I can't pass all of the test cases. I need to return true if the tree is a binary search tree, otherwise, I need to return false. Can anyone tell me what I am doing wrong?

'''
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)

推荐答案

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

You've a lot of redundant if conditions in your code. You can simplify it like so:

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).

First, check for all the None conditions. Short circuiting in python guarantees that if the first condition is False, the second will not be evaluated. This allows you to write succinct statements such as return root.left.data < root.data and checkBST(root.left).

最后，如果左节点和右节点都不是None，请不再次调用checkBST(root).这导致无限递归.

Finally, in the event that neither left nor right nodes are None, do not call checkBST(root) again. This leads to infinite recursion.

这篇关于检查树是否是二进制搜索树(BST)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！