一刷劍指offer（50）——樹中兩個結點的最低公共祖先

//GetLastCommonNode用來得到兩個路徑path1和path2的最後一個公共結點
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++;
        iterator2++;
    }
    return pLast;
}


//GetNodePath用來得到從根結點pRoot開始到達結點pNode的路徑，這條路徑儲存在path中
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;
}

//GetLastCommonParent先調用GetNodePath得到pRoot到達pNode1的路徑path1,再得到pRoot到達pNode2的路徑path2，接着調用GetLastCommonPath得到path1和path2的最後一個公共結點
//将找兩個結點最低祖先轉換稱找兩個連結清單最終公共結點
TreeNode* GetLastCommonParent(TreeNode* pRoot,TreeNode* pNode1,TreeNode* 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);
}