Python BST(Binary Search Tree) Testdome

Question

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

问题来了

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

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

例如，对于以下树：

n1（值：1，左：空，右：空） n2（值：2，左：n1，右：n3） n3（值：3，左：空，右：空）调用 contains(n2, 3) 应该 return 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

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

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

要点3：当根值小于关键值时，你应该向右走。

对您的代码进行以下更改：

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 2

你需要先检查root是不是None，然后是return False，如果是root.left is None或者root.right is None就不需要检查

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

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

你也不需要 elif 因为你 return 来自 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)

Python BST(Binary Search Tree) Testdome

BST(Binary Search Tree) Testdome in Python

python

algorithm

recursion

binary-search-tree

namedtuple