面试经典（5）--二叉树最低公共祖先LCA

题目：输入二叉树的俩个节点，求它们的最低公共祖先

算法分析：我们直接来分析O(n)的算法。

比如求节点F和节点H的最低公共祖先，先求出从根节点A到F的路径，再求出A到H的路径，那么最后一个相同的节点就是最低公共祖先。A->B->D->F和A->B->E->H，最后相同的节点事B，所以最低公共祖先是B节点。求根节点到指定节点的算法先前已经更新过了，复杂度是O(n)，所以总的时间复杂度是O(n)。

获取从根节点到指定节点的函数代码：

struct BinaryNode
{
	char value;
	BinaryNode *left;
	BinaryNode *right;
};

bool GetNodePath(BinaryNode *pRoot,BinaryNode *pNode,vector<BinaryNode*> &v)
{
	if(pRoot==NULL)
		return false;
	v.push_back(pRoot);
	if(pRoot==pNode)
		return true;
	bool found=GetNodePath(pRoot->left,pNode,v);
	if(!found)
		found=GetNodePath(pRoot->right,pNode,v);
	if(!found)
		v.pop_back();
}

求最低公共祖先节点：

BinaryNode* GetCommonParent(BinaryNode *pRoot,BinaryNode *pNode1,BinaryNode *pNode2)
{
	if(pRoot==NULL || pNode1==NULL || pNode2==NULL)
		return NULL;
	vector<BinaryNode*> v1,v2;
	GetNodePath(pRoot,pNode1,v1);
	GetNodePath(pRoot,pNode2,v2);
	BinaryNode *pLast=pRoot;
	vector<BinaryNode*>::iterator ite1=v1.begin();
	vector<BinaryNode*>::iterator ite2=v2.begin();
	while(ite1!=v1.end() && ite2!=v2.end())
	{
		if(*ite1==*ite2)
			pLast=*ite1;
		ite1++;
		ite2++;
	}
	return pLast;
}