题目

https://pintia.cn/problem-sets/994805342720868352/problems/1038430130011897856

题意

通过给出的中序序列和前序序列判断两个给定点的最近公共祖先

题解

LCA的核心思路就是当两个点都在当前根节点的左（右）边，就继续遍历左（右）子树，如果在根节点的两侧，说明该根节点就是我们要找的最近公共祖先。而这个左右就是基于中序序列判断的（详细逻辑可以到参考的链接中看一下柳神的讲解）

AC代码

#include<bits/stdc++.h>
using namespace std;
vector<int> pre,in;
map<int,int> pos;


void lca(int l,int r,int root,int x,int y)
{
	if(l>r) return;
	int inroot=pos[pre[root]],inx=pos[x],iny=pos[y];
	if(inx<inroot&&iny<inroot)
		lca(l,inroot-1,root+1,x,y);
	else if( (inx>inroot&&iny<inroot) || (inx<inroot&&iny>inroot) )
		printf("LCA of %d and %d is %d.\n",x,y,pre[root]);
	else if(inx>inroot&&iny>inroot)
		lca(inroot+1,r,root+1+(inroot-l),x,y);
	else if(inx==inroot)
		printf("%d is an ancestor of %d.\n",x,y);
	else if(iny==inroot)
		printf("%d is an ancestor of %d.\n",y,x);
}


int main()
{
	int m,n;
	scanf("%d %d",&m,&n);
	pre.resize(n+1),in.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]);
	while(m--)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		if(pos[x]==0&&pos[y]==0)
			printf("ERROR: %d and %d are not found.\n",x,y);
		else if(pos[x]==0||pos[y]==0)
			printf("ERROR: %d is not found.\n",pos[x]==0?x:y);
		else 
			lca(1,n,1,x,y);
	}
}