剑指offer——树中两个节点的最低公共祖先

代码来源与《剑指offer》

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

#include <iostream>

#include <vector>

#include <list>

using namespace std;

struct TreeNode

{

    int m_nValue;

    std::vector<TreeNode*> m_vChildren;

};

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 i1=path1.begin();

    list<TreeNode*>::const_iterator i2=path2.begin();

    TreeNode* pLast=NULL;

    while(i1!=path1.end()&&i2!=path2.end())

    {

        if (*i1==*i2)

        {

            pLast=*iterator;

        }

        i1++;

        i2++;

    }

    return pLast;

}

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);

}