1143 Lowest Common Ancestor

437 0 0

作者:kkmjy's Blog

题意：给出BST的前序序列，以及若干个查询。寻找BST中任意给定两个结点u,v的最低公共祖先(LCA)。

思路：

1、首先根据前序序列和中序序列构建好二叉搜索树（思考1：此处明明是BST，为何不在输入前序序列的过程中直接插入建树？这样做岂不是更方便？分析见最后）

2、利用二叉搜索树的性质寻找结点u和v的最低公共祖先（递归解法）（思考2：如果不是二叉搜索树，而是普通的二叉树，该如何寻找LCA？分析见最后）

1）如果根结点的值大于max(u,v)，说明u和v均在根结点的左子树，则进入根结点的左子结点继续递归

2）如果根结点的值小于min(u,v)，说明u和v均在根结点的右子树，则进入根结点的右子结点继续递归

3）剩下的情况就是，根结点的值比其中一个值大，比另外一个小，则该结点就是结点u,v的最低公共祖先了

核心代码：

//获取BST树的结点u,v的最低公共祖先
Node* getLCA(Node* root,int u,int v)
{
    if(root==nullptr) return nullptr;
    if(root->val > max(u,v)) return getLCA(root->lchild,u,v);
    else if(root->val < min(u,v)) return getLCA(root->rchild,u,v);
    else return root;
}

3、由于题目中查找的元素有可能不是树的结点，且"All the keys are in the range of int"，即结点的值可能为负，因此，额外设置一个map<int,init> mp，用于记录被查询的值是否出现过。不过，最好是使用 unordered_map ，头文件<unordered_map>，因为这里只是作为一个hash映射，不需要key值的顺序关系，用unordered_map效率更高！

代码：

#include <cstdio>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

struct Node{
    int val;
    Node *lchild,*rchild;
    Node(int v_):val(v_),lchild(nullptr),rchild(nullptr){}
};

Node* buildBiTree(vector<int>& preOrder,int preL,int preR,vector<int>& inOrder,int inL,int inR)
{
    if(preL>preR || inL>inR) return nullptr;
    int rootVal=preOrder[preL];
    Node* root=new Node(rootVal);
    int pos;
    for(pos=inL;pos<=inR;pos++)
        if(inOrder[pos]==rootVal) break;
    int leftCnt=pos-inL;
    root->lchild=buildBiTree(preOrder,preL+1,preL+leftCnt,inOrder,inL,pos-1);
    root->rchild=buildBiTree(preOrder,preL+leftCnt+1,preR,inOrder,pos+1,inR);
    return root;
}

//获取BST树的结点u,v的最低公共祖先
Node* getLCA(Node* root,int u,int v)
{
    if(root==nullptr) return nullptr;
    if(root->val > max(u,v)) return getLCA(root->lchild,u,v);
    else if(root->val < min(u,v)) return getLCA(root->rchild,u,v);
    else return root;
}

int main()
{
    //freopen("pat.txt","r",stdin);
    int queryCnt,n;
    scanf("%d%d",&queryCnt,&n);
    vector<int> preOrder(n),inOrder(n);
    unordered_map<int,int> mp;//用来判断查询值是否为树的结点
    for(int i=0;i<n;i++){
        scanf("%d",&preOrder[i]);
        mp[preOrder[i]]=1;
    }
    inOrder=preOrder;
    sort(inOrder.begin(),inOrder.end());
    Node* root=buildBiTree(preOrder,0,n-1,inOrder,0,n-1);
    int u,v;
    for(int k=0;k<queryCnt;k++){
        scanf("%d%d",&u,&v);
        if(mp[u]==0 && mp[v]!=0)
            printf("ERROR: %d is not found.n",u);
        else if(mp[u]!=0 && mp[v]==0)
            printf("ERROR: %d is not found.n",v);
        else if(mp[u]==0 && mp[v]==0)
            printf("ERROR: %d and %d are not found.n",u,v);
        else{
            Node* pNode=getLCA(root,u,v);
            int anc=pNode->val;
            if(anc==u) printf("%d is an ancestor of %d.n",u,v);
            else if(anc==v) printf("%d is an ancestor of %d.n",v,u);
            else printf("LCA of %d and %d is %d.n",u,v,anc);
        }
    }
    return 0;
}

【分析1】

如果直接在输入数据的时候插入建树，如下，会有两个测试点超时。为什么？

void insert(Node* &root,int val)
{
    if(root==nullptr){
        root=new Node(val);
        return;
    }
    if(val<root->val) insert(root->lchild,val);
    else insert(root->rchild,val);
}

for(int i=0;i<n;i++){
    scanf("%d",&val);
    insert(root,val);
    mp[val]=1;
}

当BST为极端情况时（即形成单链表的情况），若按照插入直接建树。i=0时，无需递归；i=1时，insert()递归1次，i=2时，insert()递归2次，...，i=n-1时，insert()递归n-1次，时间是O(1+2+...+n)=O(n^2)，这里n最大为10000，因此显然超时。

而利用【前序+中序-->二叉树】的方法，即使在极端情况下建树的时间复杂度也是O(n)。

【分析2】

若树为普通的二叉树，如何寻找任意两结点u,v的最低公共祖先？

1、递归解法（参考这里）

在递归函数中，我们首先判断当前结点是否为空，若为空，直接返回；或者，当前结点是否就是u或v，若是，也直接返回该结点。否则，就对其左右孩子结点分别调用递归函数。可以想到，结点u和v有以下三种情况：

　　1）u和v分别位于当前结点的左右两侧；

　　2）u和v都在当前结点的左子树中；

　　3）u和v都在当前结点的右子树中。

若u和v分别位于左右子树中，那么对左右子结点调用递归函数，会分别返回u和v结点的位置，而当前结点正好就是u和v的最小共同父结点，直接返回当前结点即可。

若u和v同时位于左子树，这里有两种情况，一种情况是left会返回u和v中较高的那个位置，而right会返回空，所以我们最终返回非空的left即可；还有一种情况是会返回u和v的最小父结点，就是说当前结点的左子树中的某个结点才是u和v的最小父结点，会被返回。

若u和v同时位于右子树，同样这里有两种情况，一种情况是right会返回u和v中较高的那个位置，而left会返回空，所以我们最终返回非空的right即可，还有一种情况是会返回u和v的最小父结点，就是说当前结点的右子树中的某个结点才是u和v的最小父结点，会被返回。

代码如下：

Node* getLCA(Node* root,int u,int v)
{
    if(root==nullptr || root->val==u || root->val==v) return root;
    Node* left=getLCA(root->lchild,u,v);
    Node* right=getLCA(root->rchild,u,v);
    if(left && right) return root;
    else return (left?left:right);
}

2、非递归解法

我在树这部分内容中讲到过后序遍历的非递归写法，这种写法有个性质就是，“当访问到结点v时，栈中存放的元素恰为结点v的所有父节点”。由此，可以想到，为了寻找结点u和v的最低公共祖先，可以非递归后序遍历该二叉树，当访问到结点u时，当前栈中的元素就是结点u的所有父节点（从下至上的），把栈中的元素拷贝至ancestor_u中；然后，继续访问，当访问到当访问到结点v时，当前栈中的元素就是结点v的所有父节点（从下至上的），把栈中的元素拷贝至ancestor_v中。找出ancestor_u和ancestor_v中的首个相同的元素，就是两者的LCA。不过，因为ancestor_u和ancestor_v中的元素是无序的，因此，这一步的时间复杂度O(n^2)，因此，这个方法是不推荐的。只是了解一下。

内容来源于网络如有侵权请私信删除

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

1143 Lowest Common Ancestor