Ant*_*ony 3 python algorithm tree
在Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力
让每个节点包含其基数列表,并执行连接,找到最长的公共前缀,然后取最后一个元素.不幸的是,我不知道有任何内置的方法来做最长的公共前缀,所以这需要手动循环.
让每个节点包含一组基础并执行集合交集,并获取最大元素.但这需要定义自定义比较运算符,我甚至不确定它是否可行.
我该怎么办？我正在寻找一些有利于简化而不是性能的东西,因此需要复杂处理的解决方案已经完成.
编辑:我发现虽然没有内置方式,但你可以使用zip在一行中做最长的公共前缀,所以它仍然相当简单.
common = [x for x in zip(*baselists) if len(set(x)) == 1][-1]
假设您无法修改树以包含深度,您可以执行以下操作:
对于每个节点,递归地向上遍历树,直到您到达根.在每个父节点上,将节点插入到a中list.这应该给你list_a和list_b.迭代最短列表,比较每个列表中的元素.当您找到一个不匹配的条目时,前一个条目是您最大的父元素.
取每个节点的深度(与根的距离).如果一个低于另一个,则从下部节点向上移动树,直到深度相等.然后检查身份,每次检查失败时在每一侧移动每个身份.
您可以使用单个while循环执行此操作.一旦你选择了同等深度的祖先:
while (ancestorA !== ancestorB) {
ancestorA = ancestorA.parent();
ancestorB = ancestorB.parent();
}
当while循环终止,ancestorA并且ancestorB将各自的共同祖先.
这不仅应该非常简单,而且还要相当快.