python最低共同祖先

概述在 Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力 >让每个节点包含其基数列表,并执行连接,找到最长的公共前缀,然后取最后一个元素.不幸的是,我不知道有任何内置的方法来做最长的公共前缀,所以这需要手动循环. >让每个节点包含一组基础并执行集合交集,并获取最大元素. 在 Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力

>让每个节点包含其基数列表,并执行连接,找到最长的公共前缀,然后取最后一个元素.不幸的是,我不知道有任何内置的方法来做最长的公共前缀,所以这需要手动循环.
>让每个节点包含一组基础并执行集合交集,并获取最大元素.但这需要定义自定义比较运算符,我甚至不确定它是否可行.

我该怎么办？我正在寻找一些有利于简化而不是性能的东西,因此需要复杂处理的解决方案已经完成.

编辑：我发现虽然没有内置方式,但你可以使用zip在一行中做最长的公共前缀,所以它仍然相当简单.

common = [x for x in zip(*baseLists) if len(set(x)) == 1][-1]

@H_502_21@解决方法 假设您无法修改树以包含深度,您可以执行以下 *** 作：

对于每个节点,递归地向上遍历树,直到您到达根.在每个父节点上,将节点插入列表中.这应该给你List_a和List_b.迭代最短列表,比较每个列表中的元素.当您找到一个不匹配的条目时,前一个条目是您最大的父元素.

总结

以上是内存溢出为你收集整理的python最低共同祖先全部内容，希望文章能够帮你解决python最低共同祖先所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。