题目：树中两个结点的最低公共祖先
该题目根据条件的不同，所使用的方案也不同。
条件一：是二叉搜索树。
方案：这种情况相对来说是最简单的，如果是二叉搜索树，则树里的数据特点比较明显。左边的比根结点小，右边的比根结点大。所以其最低的公共结点就是第一个在这两个输入节点之间的结点。
条件二：如果这棵树是一颗普通的树，可能连二叉树都不算，但是有指向父节点的指针。
方案：其实这个问题可以转化为：求两个链表的公共结点，因为有指向父节点的指针，那么给的结点就在一个链表上，我们就可以查找这两个链表的第一个公共结点。查找两个链表的公共结点，我们已经在【5】中讲的比较详细了，这里就不多做介绍了！
条件三：这棵树是一棵普通的树，可能连二叉树都不是，也没有指向父节点的指针。
方案一：由于数据不是有序，也没有指向父节点的指针，也可能是N叉树，所以我们的初步想法是，逐个结点的找，如果发现一个结点包含输入的两个结点，则顺序遍历该结点的子结点，如果子节点是最后一个包含这两个输入结点的结点，它的子结点都不包含输入的两个子结点，则说明该结点是这两个输入结点的最低公共结点。
该方案的弊端是重复计算，就像斐波拉切数列，以及判断平衡二叉树中存在的问题一样。举个例子来看吧！
以上图为例，如果我们输入的是F和H两个结点，当我们判断完A结点包含F和H两个结点后，判断A的时候，我们的遍历BDE，继续向下判断B，然后还得遍历DE，这就是一种重复。如果该树比较负责，重复的会更多，这样使的效率比较低下。
方案二：还是转化为两个链表求公共结点。这样我们就可以避免那些多余的运算。我们可以首先遍历该树，从根结点开始，到达两个输入结点就有两条路径，这样我们就可以从输入的结点开始寻找他们的第一个公共结点，就是它们的最低公共祖先结点。
还是以上图为例：一条路径为A->B->D->F，另一条路径为A->B->E->H。所以其第一个公共结点为B，那么B就是其最低的公共祖先结点。其时间复杂度，首先找路径遍历2遍，都是O(N)。然后找公共结点其时间复杂度为：O(logN)，综合其时间复杂度为：O(N)。空间复杂度为2*O(N)。 条件三中的方案二具体代码实现如下：
#include <iostream>
#include <list>
#include <vector>
using namespace std;
struct BinTree
{
int data;
BinTree *pLeft;
BinTree *pRight;
};
list<BinTree *> path1;
list<BinTree *> path2;
BinTree *pRoot1=NULL;
bool IsExistData1=true;
bool IsExistData2=true;
//递归先序创建二叉树；
void CreateTree(BinTree *&root)
{
int data;
cin>>data;
if(0==data)
root=NULL;
else
{
root=new BinTree;
root->data=data;
CreateTree(root->pLeft);
CreateTree(root->pRight);
}
}
//1.将从根结点pRoot到输入的结点值data1,data2的路径保存在链表list1和list2中；
bool GetNodePath(BinTree *root,int data1,list<BinTree*> &path)
{
if(NULL==root )
return false;
path.push_back(root);
if(root->data==data1)
return true;
else
{
bool found=false;
found=GetNodePath(root->pLeft,data1,path);
if(!found)
found=GetNodePath(root->pRight,data1,path);
if(!found)
path.pop_back();
return found;
}
}
//2.得到list1和list2公共结点；
BinTree *GetLastComNode(const list<BinTree *> &list1,const list<BinTree*> &list2)
{
list<BinTree *>::const_iterator it1=list1.begin();
list<BinTree *>::const_iterator it2=list2.begin();
BinTree *pLast=NULL;
while(it1!=list1.end() && it2!=list2.end())
{
if(*it1 == *it2)
pLast=*it1;
it1++;
it2++;
}
return pLast;
}
//3.组合1,2，返回公共结点；
BinTree *GetLastCommParent(BinTree *root,int data1,int data2)
{
if(NULL==root)
return NULL;
//得到路径
if(!GetNodePath(root,data1,path1))
{
IsExistData1=false;
return NULL;
}
if(!GetNodePath(root,data2,path2))
{
IsExistData2=false;
return NULL;
}
//得到最低公共祖先；
return GetLastComNode(path1,path2);
}
void PreOrder(BinTree *root)
{
if(root)
{
cout<<root->data<<" ";
PreOrder(root->pLeft);
PreOrder(root->pRight);
}
}
void InOrder(BinTree *root)
{
if(root)
{
InOrder(root->pLeft);
cout<<root->data<<" ";
InOrder(root->pRight);
}
}
void DestoryBinTree(BinTree *root)
{
if(root)
{
DestoryBinTree(root->pLeft);
DestoryBinTree(root->pRight);
delete root;
root=NULL;
}
}
int main()
{
int da1,da2;
BinTree *result=NULL;
CreateTree(pRoot1);
cout<<"前序遍历：";
PreOrder(pRoot1);
cout<<endl;
cout<<"中序遍历：";
InOrder(pRoot1);
cout<<endl;
while(1)
{
cin>>da1>>da2;
if(0==da1 || 0==da2 )
break;
result=GetLastCommParent(pRoot1,da1,da2);
path1.clear();
path2.clear();
if(IsExistData1&& IsExistData2)
cout<<da1<<"和"<<da2<<"的最低公共祖先是："<<result->data<<endl;
else
{
if(!IsExistData1)
cout<<da1<<"数据不存在！"<<endl;
else
cout<<da2<<"数据不存在！"<<endl;
}
}
DestoryBinTree(pRoot1);
system("pause");
return 0;
}
运行结果：
树的形状：
结果：
| 
转播
