Python 中的 BST（二叉搜索树）Testdome

Question

我需要有关 test-dome 中发布的问题的解决方案。

问题来了

二叉搜索树（BST）是一种二叉树，其中每个节点的值都大于或等于该节点左子树中所有节点的值，并且小于该节点右子树中所有节点的值。

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

例如，对于以下树：

n1（值：1，左：空，右：空） n2（值：2，左：n1，右：n3） n3（值：3，左：空，右：空） 调用 contains(n2, 3) 应返回 True，因为根位于 n2 的树包含数字 3。

以下是我的答案。 我正在用Python编程。

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

现在我通过了33.3%，请帮助我通过100%

Answer 1

需要先检查root是否为

None

，然后返回

False

，不需要检查是否为

root.left is None

或

root.right is None

然后就像提到的其他答案一样，您的代码看起来总是正确的。

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

而且您也不需要

elif

因为您是从

if

返回的

有了这些变化：

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)

Answer 2

第1点：你总是走右子树。根值是否低于或高于密钥。

第2点：当根值高于键时，你应该向左走。

第3点：当根值低于key时，你应该向右走。

在代码中进行以下更改：

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

Answer 3

这样我的测试就100%通过了。

import collections
Node = collections.namedtuple('Node', ['left', 'right', 'value'])
def contains(root, value):  
if value == root.value:
    return True
elif root.value > value:
    if root.left != None:
        return contains(root.left, value)
elif root.value < value:
    if root.right != None:
        return contains(root.right, value)
return False
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, 3))