查找与树中任何节点的距离

Question

我正在尝试从以下树中的其他节点获取节点的深度。我有一个包含父子关系的列表：

Parent -> Children
[2] -> [0]
[1] -> [2,5]
[5] -> [3,4,6]

我想找到一个节点与其他节点的深度/距离。 因此，从节点[5]，depth[]={3,1,2,1,1,0,1}

我目前有：

def get_depth(self,idx,depth):
self.depth[idx]=depth
for child in self.sentence_prop.words[idx].children:
get_depth(child[0],depth+1)
return

其中 idx=[5]和初始depth=0。我只为孩子这样做，但我不确定如何为父母做。

Answer 1

我希望这可以解决您的问题。

1( 2 个节点之间的距离由以下公式给出：

Dist(n1， n2( = Dist(root， n1( + Dist(root，

n2( - 2*Dist(root， 信用证(

这里 lca ： n1 和 n2 的最低共同祖先。这适用于任何通用树。

2(你需要做什么：

1. 存储与要查找距离的每个节点对应的路径 之
2. 循环访问路径以查找公共路径长度。
3. return (len(path1)+len(path2)-2*(common_path_length))

二叉树这个概念的实现在这里