二叉树-最低公共父节点（2）

2016-03-10 本文已影响114人 AwesomeAshe

在上一篇文章中我们用的是暴力的遍历判断的方法，然而在树有关的题目中，保存路径也是一个很常用的思路，比如求两个节点的最短路径，求路径长度。
并且为了改善算法的复杂度，我们可以尝试减少遍历的次数，上一种方法中，我们遍历了两次，这次，我们试着保存遍历的路径，然后求两个路径的公共节点。
首先我们有一个getNodePath 函数，该函数会将从头结点到给定节点的路径保存，然后有一个lastCommonNode函数求路径的公共节点。

首先我们看这个函数，这个函数的设计的思路值得我学习。

返回量：该函数返回的是布尔型变量，表示该节点是否在包含指定node的路径上。
为什么要如此选取呢？为什么不直接返回一个list的指针？我们要通过这个函数得到list，为什么要作为一个参数传进去而不是作为返回量？
我们看函数的结构，和大多数遍历树的函数一样，该函数也是递归的。我们的参数之一是树的根节点，意思是从这个节点往下遍历。
整个函数有四个分支，分别是
1，该根节点就是要找的节点，返回true
2，否则在左子树寻找
3，否则在右子树寻找
4，要找的节点不在当前根节点的下面。此时删除掉路径中存储的当前节点。
由此，我们遍历整个树之后留下的节点就是路径

bool getNodePath(node* ptree, node* pnode,std::list<node*>& path)
{
    if (ptree == pnode)
        return true;

    path.push_back(ptree);
    //在递归中，我们只关心这一轮要处理的节点，因此只需要把ptree放进去而不需要在left和right中加入push_back

    bool found = false;
    if (ptree->lnode)
    {
        found = getNodePath(ptree->lnode, pnode, path);
    }
    if (!found&&ptree->rnode)
    {
        found = getNodePath(ptree->rnode, pnode, path);
    }
    if (!found)
        path.pop_back();
    return found;
}

由于我对递归函数还是不太熟悉，在设想的时候总是会在左右子树分支的函数里面加上path.push_back(tree->left) ，总是觉得处理当前节点就要有显式的语句，但是实际上后面的递归调用会把这个节点加进去的，如果还写，那就是重复了。
在递归的函数中我们应该这样想，我们只处理当前节点，当前节点的子节点留给递归就行了。

下面是完整的函数：

//way2,get the path , the get the last common node of two paths
#include <list>

bool getNodePath(node* ptree, node* pnode,std::list<node*>& path)
{
    if (ptree == pnode)
        return true;

    path.push_back(ptree);
    //在递归中，我们只关心这一轮要处理的节点，因此只需要把ptree放进去而不需要在left和right中加入push_back

    bool found = false;
    if (ptree->lnode)
    {
        found = getNodePath(ptree->lnode, pnode, path);
    }
    if (!found&&ptree->rnode)
    {
        found = getNodePath(ptree->rnode, pnode, path);
    }
    if (!found)
        path.pop_back();
    return found;
}
node* lastCommonNode_l(std::list<node*>& path1, std::list<node*>& path2)
{
    node* path = NULL;
    std::list<node*>::const_iterator ptr1=path1.begin();
    std::list<node*>::const_iterator ptr2 = path2.begin();
    while (ptr1 != path1.end() && ptr2 != path2.end())
    {
        if (*ptr1 == *ptr2)
            path = *ptr1;//why *ptr
            //we do not return here since we need the last common node 
        ptr1++;
        ptr2++;
    }
    return path;//attention
    
}
node* LastCommonNode(node* tree, node* node1, node* node2)
{
    if (tree == NULL || !node1 || node2)
        return;

    std::list<node*> path1;
    std::list<node*> path2;
    getNodePath(tree, node1, path1);
    getNodePath(tree, node1, path2);

    return lastCommonNode_l(path1, path2);
}

文章参考何海涛大神文章

二叉树-最低公共父节点（2）

猜你喜欢

热点阅读