PAT甲级1151.

目录

A1151

题目

样例

输入:

6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99

输出:

LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

思路和坑点

  思路:
  根据先序和中序的关系,可以直到在中序中,LCA一定在U和V结点的中间,或者是其中一个,但是要找到最底层的LCA则需要递归到最底层的子树上去查找,具体实现见代码及注释。

AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> pre,in;                                         //先序顺序为根、左、右  中序序列为左、根、右
unordered_map<int,int> pos;                                 //记录结点再中序序列中的位置
void lca(int prroot,int inl,int inr,int a,int b){
    if(inl>inr)    return;                                  //当序列长度为0时返回
    int inroot=pos[pre[prroot]],ain=pos[a],bin=pos[b];      //确定先序的根,a,b在中序序列的位置
    if(ain<inroot&&bin<inroot)                              //如果a,b都在根的左子树上,则递归向左子树查询
        lca(prroot+1,inl,inroot-1,a,b);
    else if((ain<inroot&&bin>inroot)||(ain>inroot&&bin<inroot))//如果a,b在根的左右两侧,说明根为LCA
        printf("LCA of %d and %d is %d.\n",a,b,in[inroot]);
    else if(ain>inroot&&bin>inroot)                         //如果都在右子树,则递归向右子树查询
        lca(prroot+1+inroot-inl,inroot+1,inr,a,b);
    else if(ain==inroot)                                    //如果其中有一个在根的位置上,则输出对应信息
        printf("%d is an ancestor of %d.\n",a,b);
    else if(bin==inroot)
        printf("%d is an ancestor of %d.\n",b,a);
}        
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int m,n,a,b;
    scanf("%d%d",&m,&n);
    in.resize(n+1),pre.resize(n+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&in[i]);
        pos[in[i]]=i;
    }
    for(int i=1;i<=n;i++)    scanf("%d",&pre[i]);           //读入序列并记录每个结点在中序序列的位置
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        if(pos.find(a)==pos.end()&&pos.find(b)==pos.end())  //如果两者都不存在
            printf("ERROR: %d and %d are not found.\n", a, b);
        else if(pos.find(a)==pos.end()||pos.find(b)==pos.end())//如果有一个不存在
            printf("ERROR: %d is not found.\n", pos.find(a)==pos.end()?a:b);
        else 
            lca(1,1,n,a,b);                                 //如果凑存在则查找LCA
    }
    return 0;    
}