利用二叉树的非递归后序遍历求解最近公共祖先问题

通过上一篇的博客我们知道，可以利用栈来实现二叉树的后序遍历。其实这里有一个性质，就是当使用非递归后序遍历时，栈中的元素就是当前节点到根节点的路径。利用这个规律，我们就可以求解最近公共最先问题了。

算法

找出两个节点各自到根节点的路径。这里利用非递归后序遍历二叉树，既可以找到两个节点到根节点的路径。根据路径找出最近的公共祖先。首先根节点肯定是他们的祖先，可以从跟节点开始查找，直到最后一个相同的树节点，就是他们的公共祖先了。

实现

///求两个节点的最大公共祖先 void BiTree::ancestor(char A,char B){ vector<BiNode *> pathA,pathB; ///非递归后序遍历 ///p表示当前树节点指针， ///r表示最近访问的树节点指针 BiNode *p,*r; r = NULL; p = root; stack<BiNode*> my_stack; int pathCnt=0; while(p!=NULL || !my_stack.empty()){ if(p){ ///一直走到树的最左边 my_stack.push(p); p=p->lchild; } else{ p=my_stack.top(); ///如果右子树没有遍历，遍历右子树 if(p->rchild!=NULL && p->rchild!=r){ p=p->rchild; my_stack.push(p); ///注意这里需要向左转，因为如果不向左转， ///将会遍历右子树节点两边 p=p->lchild; } ///否则遍历根节点 else{ p=my_stack.top(); my_stack.pop(); ///记录A的路径 if(p->data==A){ cout<<"找到"<<A<<"的路径："<<endl; pathA.push_back(p); while(!my_stack.empty()){ p=my_stack.top(); my_stack.pop(); pathA.push_back(p); } ///恢复my_stack for(int i=pathA.size()-1;i>=0;i--){ cout<<pathA[i]->data<<' '; my_stack.push(pathA[i]); p=pathA[i]; } p=my_stack.top(); my_stack.pop(); cout<<endl; ///找到了一个节点的路径 ++pathCnt; } ///记录B的路径 if(p->data==B){ cout<<"找到"<<B<<"的路径："<<endl; pathB.push_back(p); while(!my_stack.empty()){ p=my_stack.top(); my_stack.pop(); pathB.push_back(p); } ///恢复my_stack for(int i=pathB.size()-1;i>=0;i--){ cout<<pathB[i]->data<<' '; my_stack.push(pathB[i]); p=pathB[i]; } p=my_stack.top(); my_stack.pop(); cout<<endl; ///找到了另一个节点的路径 ++pathCnt; } ///如果找到了两个节点的路径就不遍历了 if(pathCnt==2) break; ///更新最近遍历的节点 r=p; ///将遍历后的节点设为NULL，进行下一个节点的遍历 p=NULL; } } } BiNode *common_node; int i,j; i=pathA.size()-1; j=pathB.size()-1; while(i>=0 && j>=0 && pathA[i]==pathB[j]){ ///更新公共结点 common_node = pathA[i]; --i,--j; } cout<<"结点"<<A<<"和节点"<<B<<"的最近公共祖先是"<<common_node->data<<"。"<<endl; }

测试

#include <iostream> #include "BiTree.h" using namespace std; int main() { BiTree a; string s; s="ABD##E#F##C##"; a.createBiTree(s); a.ancestor('D','D'); cout<<"--------------------"<<endl; a.ancestor('D','F'); cout<<"--------------------"<<endl; a.ancestor('D','C'); cout<<"--------------------"<<endl; return 0; }