我正在尝试获取树中两个节点的最不共同祖先。我已经尝试过,但问题是如果一个节点是其他节点的后代
,我无法获得 LCA。
我尝试解决它,然后它仅适用于后代节点。不知道如何进行。
Node* Tree::LCA(Node* root, Node* n1, Node* n2) {
list<Node*> a1,a2;
while(n1 != NULL) {
a1.push_back(n1->parent);
n1 = n1->parent;
}
while(n2 != NULL) {
a2.push_back(n2->parent);
n2 = n2->parent;
}
while(!a1.empty() && !a2.empty() && a1.back() == a2.back()) {
a1.pop_back();
a2.pop_back();
}
if( a1.back() != a2.back()) {
Node* rn = a1.back();
cout << " LCA of r-U and r_v is " << rn->index << endl;
}
}
最佳答案
您从 n1->parent
和 n2->parent
开始推送。相反,在推送他们的 parent 和其他祖先之前,还要推送 n1
和 n2
。所以你的代码应该是:
Node* Tree::LCA(Node* root, Node* n1, Node* n2) {
list<Node*> a1,a2;
a1.push_back(n1); // line to be added
while(n1 != NULL) {
a1.push_back(n1->parent);
n1 = n1->parent;
}
a2.push_back(n2); // line to be added
while(n2 != NULL) {
a2.push_back(n2->parent);
n2 = n2->parent;
}
// rest of code
关于c++ - LCA 后代节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15383055/