即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

树中两结点的最低公共祖先(C++实现)

编程语言 xy913741894 17℃ 0评论
本文目录
[隐藏]

题目是,输入两个树结点,求它们的最低公共祖先

首先,要说明的是,这是一组题目,根据剑指Offer上所讲的,这道题可能会分好几种情况,因此,如果在面试时候遇到,我们需要和面试官沟通,而不是一上来就写代码。

1.1. 如果给定树是二叉搜索树

这里写图片描述

二叉搜索树(又叫二叉排序树),中序遍历是可以得到有序序列的,因此,我们可以利用这个性质来解题。

假设给定的两个树结点为4,1,根据图示,显然3为最低公共祖先;


假设给定的两个树结点为4,3,根据图示,显然3为最低公共祖先;


假设给定的两个树结点为2,1,根据图示,显然2为最低公共祖先;


假设给定的两个树结点为6,8,根据图示,显然7为最低公共祖先;


假设给定的两个树结点为8,1,根据图示,显然5为最低公共祖先;


因此我们发现,公共祖先的值都是在给定两个树结点的范围之内。

所以,我们可以由根结点遍历,如果当前结点的值比两结点大,需要到当前结点的左子树中找,如果当前结点的值比两结点小,需要到当前结点的右子树中找,仅当当前结点的值在两结点的范围内(等于也算)

代码比较简单,如下:

Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;

    if (root->data > n1->data && root->data > n2->data)
        return FindLowestCommonAncestor(root->left, n1, n2);
    else if (root->data < n1->data && root->data < n2->data)
        return FindLowestCommonAncestor(root->right, n1, n2);
    else
        return root;
}

2.2. 如果给定树由指向父节点的指针

这里写图片描述

假设我们给定的结点为G,E,显然由图示,最低公共祖先为B。

由于有了指向父结点的指针,因此我们可以由G,E出发,找到最低公共祖先,所以此题其实本质是两个链表的第一个公共结点。

链表求交问题不难,有不少方法,比如可以先把G,E到根节点A所经过的所有结点压栈,此时有两个序列,


GDBA,EBA,两栈栈顶相同Pop,最后一个相同的结点即为所求结果,这样的算法需要借助两个栈(其他类似容器也可以)。

在这里,我给出一种不需要借助容器的算法,分别由G,E遍历到根节点得到各自的长度,4和3,让长度长一点的那个链表先走一步,比如G先走到D,此时序列为DBA和EBA,同时走,遇到相同的结点即为所求结果。

代码如下:

Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;

    Node* p1 = n1;
    Node* p2 = n2;
    int count1 = 0; //求n2到根节点的长度
    int count2 = 0; //求n2到根节点的长度
    while (p1 != NULL)
    {
        ++count1;
        p1 = p1->next;
    }

    while (p2 != NULL)
    {
        ++count2;
        p2 = p2->next;
    }

    if (count1 >= count2)
    {
        int n = count1 - count2;
        p1 = n1;
        p2 = n2;
        while (n--)
        {
            p1 = p1->next;
        }
    }
    else
    {
        int n = count2 - count1;
        p1 = n1;
        p2 = n2;
        while (n--)
        {
            p2 = p2->next;
        }
    }

    while (p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

3.3. 如果给定树是普通的二叉树

我们往往可能遇到更一般的情况,也就是给定树只是普通的二叉树。那么这道题如何解?

这里写图片描述

我们还是以之前的图来看,不过需要注意的是此时没有指向父节点的指针。

3.1.3. 1一般解法

其实,我们可以类比第一种情况(二叉搜索树)的解法,我们举例来分析:

假设给定树结点为D,E,求最低公共结点。我们由根节点A出发,D,E都在A的左子树中,于是我们遍历到B,此时D,E分别在B的左右子树中,B即为所求答案。

假设给定树结点为E,H,我们由A结点出发,发现E,H都在它的左子树中,于是我们遍历到B,发现他们都在B的右子树中,于是我们遍历到了E,此时E为所求答案。

因此,我们发现,如果给定的两个树结点都在当前结点的左子树里面,最低公共祖先必在左子树中,如果给定的两个树结点都在当前结点的右子树里面,最低公共祖先必在右子树中,如果不满足这两个条件,当前结点即为最低公共祖先。

思路有了,我们需要完成代码

//判断某个结点在当前树中
bool IsInTheBinaryTree(Node* root, Node* n)
{
    if (root == NULL || n == NULL)
        return false;
    if (root == n)
        return true;
    bool found = IsInTheBinaryTree(root->left, n);
    if (!found)
        found = IsInTheBinaryTree(root->right, n);
    return found;
}


Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;
    //都在左子树,结果必在左子树中
    if (IsInTheBinaryTree(root->left, n1) && IsInTheBinaryTree(root->left, n2))
        return FindLowestCommonAncestor(root->left, n1, n2);
    //都在右子树,结果必在右子树中
    else if (IsInTheBinaryTree(root->right, n1) && IsInTheBinaryTree(root->right, n2))
        return FindLowestCommonAncestor(root->right, n1, n2);
    else
        return root;
}

3.2.3. 2更快的解法

我们已经完成基本功能了,然而我们仔细分析下代码发现,我们判断某个结点在树中递归了一次树,求公共结点又递归了一次树,这样子会对某些结点重复遍历很多次,效率比较低,能否有一个更好的算法?

为了解决这个问题,我们需要保存从根节点到两个给定树结点的路径,这样子由变成了求链表的最后公共结点了。还是拿上面的图举例:

这里写图片描述

求G,E的最低公共祖先。

由A到G的路径为:ABDG


由A到E的路径为:ABE

如果看作是链表,我们只需要求最后一个公共交点了,当然借助其他类似容器也是同样的道理,这里我使用vector保存路径。

bool GetPath(Node* root, Node* n, vector& v)
{
    if (root == NULL || n == NULL)
        return false;
    if (root == n)
    {
        v.push_back(root);
        return true;
    }
    v.push_back(root);

    bool found = false;
    found = GetPath(root->left, n, v);

    if (!found)
        found = GetPath(root->right, n, v);

    if (!found)
        v.pop_back();
    return found;
}



Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    //参数有一个为空返回NULL
    if (root == NULL || n1 == NULL || n2 == NULL)
        return NULL;
    vector v1;
    bool hasPath1 = GetPath(root, n1, v1);
    vector v2;
    bool hasPath2 = GetPath(root, n2, v2);

    if (hasPath1 && hasPath2)
    {
        int i = 0;
        while (v1[i] == v2[i])
        {
            ++i;
        }
        return v1[i - 1];
    }
    else
    {
        return NULL;
    }

}

转载请注明:CodingBlog » 树中两结点的最低公共祖先(C++实现)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情