先输入前序遍历序列（扩展二叉树 ），然后求两个节点的最近公共最先，由后续遍历算法改进而来。
#include <iostream>
#include <stack>
using namespace std;
struct Node{
char data;
Node * left;
Node * right;
};
void Create(Node * &root)
{
//qian xu jian li
char ch;
cin>>ch;
if(ch=='#')
{
root=NULL;
return;
}
root =new Node;
root->data=ch;
Create(root->left);
Create(root->right);
}
bool Search(Node * & result,char a,char b,Node * root)
{
if(root==NULL) return false;
bool flag1=false,flag2=false;
flag1=Search(result,a,b,root->left);
if(!result)
flag2=Search(result,a,b,root->right);
if(!result)
{
if((root->data==a||root->data==b)&&(flag1||flag2))
result=root;
else if(flag1&&flag2)
result=root;
}
return flag1||flag2||root->data==a||root->data==b;
}
Node * FindAncestor(char m,char n,Node * root)
{
Node * result=NULL;
Search(result,m,n,root);
return result;
}
void main()
{
Node * root;
Create(root);
Node * t;
t=FindAncestor('M','N',root);
if(t)
cout<<"'M' and 'N' ,Their Ancestor Node Data Is: "<<t->data;
::system("pause");
}
