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

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

算法

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

实现

///求两个节点的最大公共祖先
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;
}