最低共同祖先算法

所以我一直在研究实现最低共同祖先算法。我研究了许多不同的算法（主要是 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
}

编辑 2012 年 5 月 27 日：处理一个节点是另一个节点的后代的情况，否则会导致尝试pop()一个空栈。感谢该死的指出这一点。 （我还意识到跟踪单个oldNode.)