|
题目：求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode *>&path)
{
if(pRoot == pNode)
return true;
path.push_back(pRoot);
bool found = false;
vector<TreeNode*>::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* GetLastCommonNode
(
const list<TreeNode*>& path1;
const list<TreeNode*>& path2
)
{
list<TreeNode*>::const_iterator iterator1 = path1.begin();
list<TreeNode*>::const_iterator iterator2 = path2.begin();
TreeNode* pLast = NULL;
while(iterator1 != path1.end() && iterator2 != path2.end()){
if(*iterator1 == *iterator2)
pLast = *iterator1;
iterator1++;
itreator2++;
}
return pLast;
}
TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1,
TreeeNode* pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
list<TreeNode*> path1;
GetNodePath(pRoot, pNode1, path1);
list<TreeNode*> path2;
GetNodePath(pRoot, pNode2, path2);
return GetLastCommonNode(path1, path2);
}
代码中GetNodePath用来得到从根结点pRoot开始到达结点pRoot的路径，这条路径保存在path中。函数GetCommonNode用来得到两个路径path1和path2的最后一个公共结点。函数GetLastCommonParent先调用GetNodePath得到pRoot到达pNode1的路径path1，再得到pRoot到达pNode2的路径path2，接着调用GetLastCommonPath得到path1和path2的最后一个公共结点，即我们要找的最低公共祖先。
| 
转播
