查找二进制搜索树从根到特定关键字的距离

Question

def distance(self, rootOfTree, key):
if rootOfTree is None:
return -1
totalDist = -1
if rootOfTree.key is key:
return totalDist + 1
else:
totalDist = self.distance(rootOfTree.left, key)
if totalDist >= 0:
return totalDist + 1
totalDist = self.distance(rootOfTree.right, key)
if totalDist >= 0:
return totalDist + 1
return totalDist

嗨，我试图通过递归来编码，通过查找从根到"key"参数中给定的特定节点的距离。但我只能在函数中输入两个参数，这是我的BST的根和我想找到的键。是否可以只指定"键"并遍历BST并在功能中找到"键">

这是我的代码的第二部分

print("Depth:", bst.distance(root, "I"))

Answer 1

距离等于为了找到关键节点而需要追求的深度。您必须在每个级别中增加一个，但前提是该级别包含密钥。

class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None
def distance(root, key):
if root is None:
return -1
if root.data is key: # it's the key
return 0
else:
dl = distance(root.left, key)
dr = distance(root.right, key)
if dl != -1:
return 1 + dl
elif dr != -1:
return 1 + dr
else: # both are -1
return -1

用于测试：

root = Tree()
root.data = "1"
root.left = Tree()
root.left.data = "2"
root.right = Tree()
root.right.data = "3"
root.left.left = Tree()
root.right.left = Tree()
root.left.right = Tree()
root.right.right = Tree()
root.left.left.data = "4"
root.left.right.data = "5"
root.right.left.data = "6"
root.right.right.data = "7"
distance(root, "1")
distance(root, "2")
distance(root, "3")
distance(root, "4")

结果：

>>> distance(root, "1")
0
>>> distance(root, "2")
1
>>> distance(root, "3")
1
>>> distance(root, "4")
2
>>> distance(root, "7")
2
>>> distance(root, "8")
-1