有没有办法改进我的二叉搜索树问题的 py3 代码?

Question

我正在研究一个关于 BST 的 python3 问题，来自 https://www.testdome.com/questions/python/binary-search-tree/24973?visibility=1&skillId=9：

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

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

例如，对于以下树：

• n1(值：1，左：空，右：空)
n2(
• 值：2，左：n1，右：n3)
• n3(值：3，左：空，右：空)

调用 contains(n2， 3) 应该返回 True，因为根位于 n2 的树包含数字 3。

我的代码是：

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

它可以工作，但网站只给了我 33 分。我发现了一些类似的问题，但它们是基于 c++ 的。我想知道有没有办法改进我的代码以获得基于 python3 的更好分数？

谢谢！！

Answer 1

你的代码永远不会返回False，所以python会自动返回一个None。只需在函数的最后一行添加一个return False就足够了contains。

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