最低共同祖先算法

Question

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

}       

Answer 1

正如其他人所提到的,您的算法目前是二次的.对于小到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
}

编辑27/5/2012:处理一个节点从另一个节点下降的情况,否则会导致尝试pop()空堆栈.感谢该死的指责.(我也意识到跟踪单曲就足够了oldNode.)