How to find the first ancestor node from two leaf nodes in the same level in a binary tree
|
1
2 3 4 5 6 7 8 9 10 |
int mother{} //// an algorithm to find mother node
int n1(7), n2(11); ////two integer leaf nodes. int a1(–1), a2(–2); while(a1 != a2) { a1=mother(n1); a2=mother(n2); n1=a1; n2=a2; } |
我认为这太复杂了。我想知道是否存在任何更简单的算法？
寻找两个叶节点(LF)的第一个共同祖先(FCA)的算法
创建一个函数，该函数将返回一个向量，该向量包含到达给定叶节点所需的节点顺序列表，其中 root 是列表中的第一个节点
如果二叉树组织得当，那么它应该能够直接遍历到叶节点的最快路径。如果树没有正确组织，那么这将需要一个完整的树遍历算法来找到节点，然后确定到节点的最短路径。
调用GetPathToNode(root, leafNodeA);返回向量 pathA
调用GetPathToNode(root, leafNodeB);返回向量 pathB
创建一个函数，将比较两条路径并找到两个向量中不同的第一个元素。然后，返回第一个不同元素之前的元素。
当然，这可以通过调用第三个函数来代替第三步来进一步优化，该函数镜像GetPathToNode()，但它需要一个额外的参数：向量路径A。一旦到达第一个非公共祖先，第三个函数将退出并返回其上方的节点。
实际上，第一个共同祖先采用以节点为中心的视图(自下而上)。但是，算法必须从根开始向下移动才能找到最后一个共同祖先。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/268934.html