// 得到一条从根节点开始到目的节点的路径
bool GetNodePath(TreeNode *pRoot , TreeNode *pNode , vector<TreeNode *> &path)
{
if(pRoot == NULL)
return false;
if(pRoot == pNode)
return true;
else if(GetNodePath(pRoot->lchild , pNode , path) )
{
path.push_back(pRoot->lchild);
return true;
}
else if(GetNodePath(pRoot->rchild , pNode , path) )
{
path.push_back(pRoot->rchild);
return true;
}
return false;
}
TreeNode *GetLastCommonNode(const vector<TreeNode *> &path1 , const vector<TreeNode *> &path2)
{
vector<TreeNode *>::const_iterator iter1 = path1.begin();
vector<TreeNode *>::const_iterator iter2 = path2.begin();
TreeNode *pLast;
while(iter1 != path1.end() && iter2 != path2.end() )
{
if(*iter1 == *iter2)
pLast = *iter1;
else
break;
iter1++;
iter2++;
}
return pLast;
}
TreeNode *GetLastCommonParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
vector<TreeNode *> path1;
GetNodePath(pRoot , pNode1 , path1);
vector<TreeNode *> path2;
GetNodePath(pRoot , pNode2 , path2);
return GetLastCommonNode(path1 , path2);
}