1151 LCA in a Binary Tree （30 分)

雨点打透心脏的1/2处 2022-02-26 09:35 187阅读 0赞

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.

Given any two nodes in a binary tree, you are supposed to find their LCA.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 1,000), the number of pairs of nodes to be tested; and N (≤ 10,000), the number of keys in the binary tree, respectively. In each of the following two lines, N distinct integers are given as the inorder and preorder traversal sequences of the binary tree, respectively. It is guaranteed that the binary tree can be uniquely determined by the input sequences. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of **int**.

### Output Specification: ###

For each given pair of U and V, print in a line `LCA of U and V is A.` if the LCA is found and `A` is the key. But if `A` is one of U and V, print `X is an ancestor of Y.` where `X` is `A` and `Y` is the other node. If U or V is not found in the binary tree, print in a line `ERROR: U is not found.`or `ERROR: V is not found.` or `ERROR: U and V are not found.`.

### Sample Input: ###

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

### Sample Output: ###

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.

给出n个询问，m个结点，给出中序遍历和前序遍历->建树（考虑可能结点有负数，所以l和r指向的是位置）

把每个结点的深度都存在deep数组中，方便查询。

先判断给出的询问中结点是否存在，存在再去找公共祖先，把deep深的往上走，直到两者相同即为公共祖先。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int in[10005],pre[10005],l[10005],r[10005];
    int deep[10005],fa[10005];
    int dfs(int l1,int r1,int l2,int r2)
    {
    	if(l1>r1)return 0;
    	int root=pre[l2];
    	int p=l1;
    	while(root!=in[p])p++;
    	int cnt=p-l1;
    	l[l2]=dfs(l1,p-1,l2+1,l2+cnt);
    	r[l2]=dfs(p+1,r1,l2+cnt+1,r2);
    	return l2;
    }
    void finddeep(int x,int father,int dp)
    {
    	deep[x]=dp;
    	fa[x]=father;
    	if(l[x])finddeep(l[x],x,dp+1);
     	if(r[x])finddeep(r[x],x,dp+1);
    }
    int check(int x,int y)
    {//下层的往上走 
    	while(x!=y)
    	{
    		if(deep[x]>=deep[y])x=fa[x];
    		else y=fa[y];
    	}
    	return x;
    }
    int main()
    {
    	int n,m,i,j,x,y;
    	scanf("%d%d",&n,&m);
    	for(i=1;i<=m;i++)scanf("%d",&in[i]);
    	for(i=1;i<=m;i++)scanf("%d",&pre[i]);
    	dfs(1,m,1,m);
    	finddeep(1,-1,1);
    	while(n--)
    	{
    		scanf("%d%d",&x,&y);
    		int pos1=0,pos2=0;
    		for(i=1;i<=m;i++)
    		{//查找x,y的位置 
    			if(pre[i]==x)
    			pos1=i;
    			if(pre[i]==y)
    			pos2=i;
    		}		
    		if(pos1==0&&pos2==0)
    		printf("ERROR: %d and %d are not found.\n",x,y);
    		else if(pos1==0)
    		printf("ERROR: %d is not found.\n",x);
    		else if(pos2==0)
    		printf("ERROR: %d is not found.\n",y);
    		else
    		{
    			int lca=check(pos1,pos2);
    			if(x==y&&lca==pos1)
    			printf("%d is an ancestor of %d.\n",pre[lca],y);
    			else if(pre[lca]==x)
    			printf("%d is an ancestor of %d.\n",pre[lca],y);
    			else if(pre[lca]==y)
    			printf("%d is an ancestor of %d.\n",pre[lca],x);
    			else 
    			printf("LCA of %d and %d is %d.\n",x,y,pre[lca]);
    		}
    	}
    }