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