/*
二叉树的公共祖先系列
	1.二叉树为二叉排序树
by Rowandjj
2014/8/20
*/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *left;
	struct _NODE_ *right;
}BNode,*pBNode,*pTree;
//先序方式构造二叉树
void create(pTree *pT)
{
	int data;
	cin>>data;
	if(data =http://www.mamicode.com/= -1)>
情况2：
    二叉树是普通二叉树，但是含有指向父节点的指针.
思路：
既然含有指向父节点的指针，那么我们从输入的两个结点分别出发，得到两条到根结点的路径，然后问题转化为求两个单链表的第一个公共结点问题.
代码：
/*
二叉树公共祖先系列
	2.二叉树含有指向父节点的指针
*/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *left;
	struct _NODE_ *right;
	struct _NODE_ *parent;
}Node,*pNode,*pTree;
/*寻找最低公共祖先*/
pNode findAncestor(pTree pT,pNode pNode1,pNode pNode2)
{
	if(pT == NULL || pNode2 == NULL || pNode1 == NULL)
	{
		return NULL;
	}
	if(pT==pNode1 || pT==pNode2)
	{
		return NULL;
	}
	/* 1.计算这两个结点到根结点的路径长度 */
	int len1 = 0,len2 = 0;
	pNode pTemp = pNode1;
	while(pTemp != NULL)
	{
		pTemp = pTemp->parent;
		len1++;
	}
	pTemp = pNode2;
	while(pTemp != NULL)
	{
		pTemp = pTemp->parent;
		len2++;
	}
	/* 2.接下来相当于求两个单链表的公共结点 */
	int dif = len1-len2;
	pNode pLong = pNode1;
	pNode pShort = pNode2;
	if(dif<0)
	{
		pLong = pNode2;
		pShort = pNode1;
		dif = len2-len1;
	}
	while(dif > 0)//快指针先走dif步
	{	
		pLong = pLong->parent;
		dif--;
	}
	//两个指针同时走，第一次相遇即为最低公共祖先
	while(pLong != NULL && pShort != NULL && pLong != pShort)
	{
		pLong = pLong->parent;
		pShort = pShort->parent;
	}
	return pLong;
}
/*先序遍历*/
void display(pTree pT)
{
	if(pT == NULL)
	{
		return;
	}
	cout<<pT->data<<" ";
	if(pT->left)
	{
		display(pT->left);
	}
	if(pT->right)
	{
		display(pT->right);
	}
}
/*构建二叉树*/
void create(pTree *pT,pNode pParent)
{
	int data;
	cin>>data;
	if(data =http://www.mamicode.com/= -1)>
情况3：
树为普通二叉树，没有指向父节点的指针
思路：
首先第一步仍然需要求到输入的两个结点到根结点的一条路径，然后有了路径就好办了。
我们可以使用一个数组存放路径，然后按照先序遍历的方式得到路径，具体见代码。
代码：

/*
树中两个结点的公共祖先
	3.树为普通二叉树，没有指向父节点的指针
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _NODE_
{
	int data;
	struct _NODE_ *left;
	struct _NODE_ *right;
}Node,*pNode,*pTree;
/* 在二叉树pT中寻找从根到val的一条路径，path保存路径数组，index为当前数组下标，len为数组长度 */
bool GetNodePath(pTree pT,int val,int *path,int index,int *len)
{	
	if(pT == NULL)
	{
		*len = 0;
		return false;
	}
	path[index] = pT->data;
	
	if(pT->data =http://www.mamicode.com/= val)>