Python中BST（二叉搜索树）Testdome

Question

这里有问题

二叉搜索树(BST)是一种二叉树，其中每个节点的值大于或等于该节点左子树中所有节点的值，而小于该节点右子树中所有节点的值。

编写一个函数，根据使用的时间有效地检查给定的二叉搜索树是否包含给定的值。

import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])

def contains(root, value):
    if value == root.value:
        return True
    elif value > root.value:
        if root.right != None:
            return contains(root.right, value)
    elif value < root.value:
        if root.left != None:
            return contains(root.right, value)


n1 = Node(value=1, left=None, right=None)
n3 = Node(value=3, left=None, right=None)
n2 = Node(value=2, left=n1, right=n3)

print(contains(n2, 2))

Answer 1

您需要首先检查root是否为none，然后返回false，您不需要检查root.left是none还是root.right是none

那么就像前面提到的另一个答案一样，您的代码看起来总是正确的。

如果您要查找的值小于root值，请转到左侧。

def contains(root, value):
    if root is None:
        return False
    if value == root.value:
        return True
    if value > root.value:
        return contains(root.right, value)
    if value < root.value:
        return contains(root.left, value)