算法：树中两个结点的最低公共祖先

算法：树中两个结点的最低公共祖先

输入两个树结点，求它们的最低公共祖先。

如果是二叉树，并且是二叉搜索树，二叉树是排序过的，位于左子树的结点都比父节点要小，而位于右子树的结点都比父节点大，我们只需要从树的根结点开始和两个输入的结点进行比较。如果当前结点的值比两个结点的值都大，那么最低的共同父节点一定是在当前结点的左子树中，于是下一步遍历当前结点的左子树结点。反之则在右子树上。当找到一个结点在这两个结点的中间，那么就是最低的公共祖先。

如果该树不是二叉树，而且有指向父节点的指针。

 如果树中的每个结点（除根结点之外）都有一个指向父节点的指针，这个问题可以转换为求两个链表的第一个公共结点。假设树结点中指向父结点的指针是pParent,那么从树的每一个叶结点开始都有一个由指针pParent串起来的链表，这些链表的尾指针都是树的根节点。输入两个结点，那么这两个结点位于两个链表上，它们的最低公共祖先刚好就是这两个链表的第一个公共结点。如果输入的两个结点分别尾F和H，那么F在链表F->D->B->A上，而H在链表H->E->B->A上，这两个链表的第一个交点B刚好也是它们的最低公共祖先。

 

如果就是一个普普通通的树，没有指向父节点的指针。我们首先得到一条从根结点到树中某一结点的路径，这就要求在遍历的时候，有一个辅助内存来保存路径。比如我们用前序遍历的方法来得到从根结点到H的路径的过程是这样的：

（1）遍历A，把A存放到路径中去，路径中只有一个结点A；

（2）遍历到B，把B存到路径中去，此时路径为A->B；

（3）遍历到D，把D存放到路径中去，此时路径为A->B->D;

（4）遍历到F，把F存放到路径中去，此时路径为A->B->D->F;

  (5) F已经没有子结点，因此这条路径不可能到达结点H。把F从路径中删除，变成A->B->D;

  (6) 遍历G，和结点F一样，这条路径也不能到H。遍历完G之后，路径依旧是A->B->D;

  (7) 由于D的所有子结点都遍历过了，不可能到达结点H，因此D不在从A到H的路径中，把D从路径中删除，变成A->B;

 (8) 遍历E，把E加入到路径中，此时路径变成A->B->E

（9）遍历H，已经到达目标结点，A->B->E就是从根结点开始到H必须经过的路径。

同样，我们也可以得到从根结点开始到F必须经过的路径是A->B->D，接着，我们求出这两个路径的最后公共结点，也就是B。B这个结点也就F和H的最低公共祖先。

为了得到从根结点开始到输入的两个结点的两条路径，需要遍历两次树，每遍历依次的时间复杂度是O(n)。得到的两条路径的长度在最差情况是O(n),通常情况下两天路径的长度是O(logn)。

代码：

//树中两个结点的最低公共祖先
TreeNode* GetLastCommonNode(const list &path1, const list &path2)
{
	list::const_iterator iterator1 = path1.begin();
	list::const_iterator iterator2 = path2.begin();
	TreeNode* pLast = NULL;
	while(iterator1 != path1.end() && iterator2 != path2.end())
	{
		if(*iterator1 == *iterator2)
			pLast = *iterator1;
		iterator1++;
		iterator2++;
	}
	return pLast;
}

bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list &path)
{
	if(pRoot == pNode)
		return true;
	path.push_back(pRoot);
	bool found = false;
	vector ::iterator i = pRoot->m_vChildren.begin();
	while(!found && i < pRoot->m_vChildren.end())
	{
		found = GetNodePath(*i, pNode, path);
		++i;
	}
	if(!found)
		path.pop_back();
	return found;
}

TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode)
{
	if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
		return NULL;
	list  path1;
	GetNodePath(pRoot, pNode1, path1);
	list  path2;
	GetNodePath(pRoot, pNode2, path2);
	return GetLastCommonNode(path1, path2);
}