所以我一直在研究实现一个最低公共祖先算法。我研究了许多不同的算法（主要是Trajan解的变体或RMQ的变体）。
我使用的是非二叉树。我的树经常会在查询之间发生变化，因此预处理不一定值得。树的节点数不应超过50-75个。我想知道的是，我是应该麻烦使用他们的算法，还是只使用我自己的算法。
我的算法
myLCA(node1, node2) {
parentNode := [ ]
while (node1!=NULL) {
parentNode.push(node1)
node1 := node1.parent
}
while (node2!=NULL) {
for i in parentNode.size {
if (parentNode(i) == node2) {
return node2;
}
}
node2 := node2.parent
}
}
正如其他人所提到的，您的算法目前是二次型的。对于50-75个节点的数据集来说，这可能不是问题，但在任何情况下，都可以直接将其更改为线性时间，而无需使用任何集合或哈希表，只需记录每个节点到根的完整路径，然后从根返回并查找第一个不同的节点。紧接在前的节点（是这两个不同节点的公共父节点）是LCA:
linearLCA(node1, node2) {
parentNode1 := [ ]
while (node1!=NULL) {
parentNode1.push(node1)
node1 := node1.parent
}
parentNode2 := [ ]
while (node2!=NULL) {
parentNode2.push(node2)
node2 := node2.parent
}
while (node1 == node2 && !isEmpty(parentNode1) && !isEmpty(parentNode2)) {
oldNode := node1
node1 := parentNode1.pop()
node2 := parentNode2.pop()
}
if (node1 == node2) return node1 // One node is descended from the other
else return oldNode // Neither is descended from the other
}
EDIT 27/5/2012:处理一个节点从另一个节点下降的情况，否则会导致尝试pop()空堆栈。感谢该死的人指出这一点。（我也意识到跟踪单个oldNode就足够了。）
对于这么小的树，我不会麻烦实现任何更复杂的东西。您的解决方案看起来不错，尽管时间复杂度是根据树的高度进行平方的。如果你可以很容易地实现Set（大多数语言都内置了它），那么算法可以调整为
- 从第一个节点遍历到根，并收集集合中的所有节点
- 从第二个节点遍历到根节点，并检查当前节点是否存在于该集中。如果是，那就是共同的祖先
此外，该算法假设一个节点可以是它自己的祖先。否则，您将不得不稍微调整算法。考虑这个例子，
A
|
B
|
C
当试图找到B和C的最低共同祖先时，该算法会报告B，这可能是真的，也可能不是真的，这取决于如何定义祖先。
在不查看任何一种算法的细节的情况下，我建议查看这些算法的效率对整个应用程序的重要性，以及实现另一种算法需要付出多少努力。
在应用程序的正常（或压力）操作中，此算法将运行多少次？这会导致用户等待的时间超过必要时间吗？其他不同数量级的算法比你的算法快吗？（熟悉算法的人可以给你一个更详细的答案。）
我认为不值得优化一点代码，除非你会看到相当大的结果（有些人强烈认为过早的选择是万恶之源）
您的算法是二次型的，但可以很容易地将其设为线性。
只需为parentNode使用hashtable（即set），而不是list。因此，检查节点是否在parentNode中将是O(1)而不是O(n)。
我刚刚写了一篇博客文章，讲述了我如何实现自己的算法来解决这个问题，但它扩展到了一组任意长度的节点。你可以在这里找到它（有一个关于它如何工作的逐步图形解释）
http://bio4j.com/blog/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/
干杯，
Pablo
我有一个简单的解决方案对两个元素进行排序，最低的为左，最高的为右访问rootdef递归（根）如果root.empty，返回nil？如果左<=根&；right>=根返回根elsif left<=根&；右<=根下弯（root.left）其他的递归（root.right）结束
因此，这将检查每次遍历在平均和最差的O（log n）时间和O（log