【14】最近公共祖先问题

题目：给定一颗二叉树的两个结点，求这两个结点的最近公共祖先结点

分析：1. 假如二叉树是二叉排序树

               根据二叉排序树的性质，左子树结点的值小于根结点，根结点的值小于右子树结点的值

               那么每次只要判断，给定的两个结点的值和左右结点的值比较即可

               如果两个值都小于根结点的值，则递归到左子树

               如果两个值都大于根结点的值，则递归到右子树

               否则根结点即为最近公共祖先

            2. 如果二叉树不是排序二叉树，那么二叉树如果有一个指向父节点的指针，则题目变成求”给定两个结点，从两个结点到根结点这两条路径的第一个公共结点“和链表求公共结点一样

下面给出两种情况的代码

1. 二叉树是排序二叉树

//二叉树结点
struct BinaryTreeNode{
    int value;
	BinaryTreeNode *lsonNode;
	BinaryTreeNode *rsonNode;
};

//二叉排序树找最近公共祖先
BinaryTreeNode* FindCommonNode(BinaryTreeNode *root
	, BinaryTreeNode *nodeOne, BinaryTreeNode *nodeTwo){

	if(root == NULL || nodeOne == NULL || nodeTwo == NULL){
	   return NULL;
	}
	if((root->value > nodeOne->value)
		&& (root->value > nodeTwo->value)){ //递归到左子树
		return FindCommonNode(root->lsonNode, nodeOne, nodeTwo);
	}
	else if((root->value < nodeOne->value)
		&& (root->value < nodeTwo->value)){ //递归到右子树
			return FindCommonNode(root->rsonNode, nodeOne, nodeTwo);
	}
	else{ //当前点即为最近公共祖先
	    return root;
	}
}

2. 二叉树不是排序二叉树但是又指向父节点的指针

//二叉树的结点
struct BinaryTreeNode{
    int value;
	BinaryTreeNode *lsonNode;
	BinaryTreeNode *rsonNode;
	BinaryTreeNode *fatherNode;
};

//找最近公共祖先
BinaryTreeNode* FindCommonNode(BinaryTreeNode *root,
	BinaryTreeNode *nodeOne, BinaryTreeNode *nodeTwo){
	if(root == NULL || nodeOne == NULL || nodeTwo == NULL){
	    return NULL;
	}
	//求出两个结点到根结点root的长度
	int lenNodeOne = 0;
	int lenNodeTwo = 0;

	BinaryTreeNode *tmpNode = nodeOne;
	while(tmpNode != NULL){
	    ++lenNodeOne;
		tmpNode = tmpNode->fatherNode;
	}
	tmpNode = nodeTwo;
	while(tmpNode != NULL){
	    ++lenNodeTwo;
		tmpNode = tmpNode->fatherNode;
	}
	//让长的链先走几步
	BinaryTreeNode *pNodeOne = nodeOne;
	BinaryTreeNode *pNodeTwo = nodeTwo;
	if(lenNodeOne > lenNodeTwo){
		while(lenNodeOne > lenNodeTwo){
		     --lenNodeOne;
			 pNodeOne = pNodeOne->fatherNode;
		}
	}
	else{
	    while(lenNodeOne < lenNodeTwo){
		     --lenNodeTwo;
			 pNodeTwo = pNodeTwo->fatherNode;
		}
	}
	//两个指针一起走
	while((pNodeOne != pNodeTwo) && (pNodeOne != NULL) && (pNodeTwo != NULL)){
		pNodeOne = pNodeOne->fatherNode;
		pNodeTwo = pNodeTwo->fatherNode;
	}
	//如果两个相等说明有公共结点
	if(pNodeOne == pNodeTwo){
	    return pNodeOne;
	}
	else{
	    return NULL;
	}
}