python最低共同祖先

发布时间：2020-12-20 12:28:51 所属栏目：Python 来源：网络整理

导读：在 Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力让每个节点包含其基数列表,并执行连接,找到最长的公共前缀,然后取最

在 Python中实现最低共同祖先的最简单方法是什么？我有一个树,每个节点都有一个指向其父节点的节点,我希望能够找到给定两个节点的第一个共同祖先.我想出了几个想法,但没有一个特别有吸引力

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

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

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

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

假设您无法修改树以包含深度,您可以执行以下操作：

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!