所以我一直在研究实现最低公共(public)祖先算法。我研究了许多不同的算法(主要是 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
就足够了。)
关于algorithm - 最低共同祖先算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6338487/