剑指Offer学习总结-树中两个结点的最低公共祖先

本系列为剑指Offer学习总结，主要是代码案例的分析和实现：
书籍链接：http://product.dangdang.com/24242724.html
原作者博客：http://zhedahht.blog.163.com/blog/static/254111742011101624433132/
原作者博客链接有完整的项目代码下载。

---

树中两个结点的最低公共祖先

题目

题目： 树中两个节点的最低公共祖先。此树不是二叉树，并且没有指向父节点的指针。

树的节点定义：

struct TreeNode 
{
    int                    m_nValue;    
    std::vector<TreeNode*>    m_vChildren;    
};

假设还是输入结点F和H .

严谨分析的解法

我们首先得到一条从根结点到树中某一结点的路径，这就要求在遍历的时候，有一个辅助内存来保存路径．
比如我们用前序遍历的方法来得到从根结点到H 的路径的过程是这样的：
（1）遍历到A，把A 存放到路径中去，路径中只有一个结点A;
( 2）遍历到B，把B 存到路径中去，此时路径为A->B;
( 4）遍历到F，把F 存放到路径中去，此时路径为A->B->D->F;
( 6）遍历G. 和结点F 一样，这条路径也不能到达H. 边历完G 之后，路径仍然是A->B->D;
( 7）由于D 的所有子结点都遍历过了，不可能到这结点H，因此D 不在从A 到H 的路径中，把D 从路径中删除，变成A->B;
( 8）遍历E，把E 加入到路径中，此时路径变成A->B->E,
( 9）遍历H，已经到达目标给点， A->B->E 就是从根结点开始到达H 必须经过的路径。

　　同样，我们也可以得到从根结点开始到达F 必须经过的路径是A->B功。接着，我们求出这两个路径的最后公共结点，也就是B. B这个结点也是F 和H 的最低公共祖先．

　　为了得到从根结点开始到输入的两个结点的两条路径，需要追历两次树，每边历一次的时间复杂度是O(n）.得到的两条路径的长度在最差情况时是0（时，通常情况丁两条路径的长度是O(logn).

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++;
        iterator2++;
    }

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