1151 LCA in a binary tree (30 points)

maxmin

1151 LCA in a Binary Tree (30 branch )

title

Give the middle order and pre order sequences of binary tree , Give more n logarithm , Each pair has two numbers , Ask the deepest common ancestor of these two numbers .

Ideas

First, create a tree in the order of the first and middle , Then go to the tree to find the common ancestor of the two points .

Code

#include<stdio.h>
#include<vector>
#include<string.h>
#include<map>
using namespace std;
typedef struct node{
    
	int data;
	node *lchild,*rchild;
}node;
map<int,node*>mp;
int in[1000007],pre[1000007];
node* build(int inl,int inr,int prl,int prr)
{
    
	if(inl>inr||prl>prr){
    
		return NULL;
	}
	node* root=new node;
	int temp,ky;
	root->data=in[inl];
	for(int i=prl;i<=prr;i++){
    
		if(pre[i]==in[inl]){
    
			temp=i;
			break;
		}
	}
    mp[in[inl]]=root;
	ky=temp-prl;
	root->lchild=build(inl+1,inl+ky,prl,temp-1);
	root->rchild=build(inl+1+ky,inr,temp+1,prr);
	return root;
}
node* lcd(node* root,node* a,node* b)
{
    
	if(root==NULL|root==a||root==b){
    
		return root;
	}
	node* l=lcd(root->lchild,a,b);
	node* r=lcd(root->rchild,a,b);
	if(l==NULL){
    	// If on both sides, the root node will be returned , The one on one side will return to the child node .
		return r;
	}
	if(r==NULL){
    
		return l;
	}
	return root;
}
int main()
{
    
	int m,n,a,b;
	node *root;
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++){
    
		scanf("%d",&pre[i]);
	}
	for(int i=0;i<n;i++){
    
		scanf("%d",&in[i]);
	}
	root=build(0,n-1,0,n-1);
	for(int i=0;i<m;i++){
    
		scanf("%d%d",&a,&b);
		if(!mp[a]&&!mp[b]){
    
			printf("ERROR: %d and %d are not found.\n",a,b);
		}else if(!mp[a]){
    
			printf("ERROR: %d is not found.\n",a);
		}else if(!mp[b]){
    
			printf("ERROR: %d is not found.\n",b);
		}else{
    
			node* p=lcd(root,mp[a],mp[b]);
			if(p->data==a){
    
				printf("%d is an ancestor of %d.\n",a,b);
			}else if(p->data==b){
    
				printf("%d is an ancestor of %d.\n",b,a);
			}else{
    
				printf("LCA of %d and %d is %d.\n",a,b,p->data);
			}
		}
	}
	return 0;
}