L2-3 romantic silhouette (25 points)

“ Profile ” Is to observe what the object sees from the left or right . For example, the silhouette of the boy in the above picture is what he looks at from his right side , It's called “ Right side view ”; The girl's silhouette looks from her left , It's called “ Left view ”.

520 You are still playing this day , Just hold a binary tree and look left and right ……

We will the of binary tree “ Profile ” Defined as a sequence of all nodes visible from one side from top to bottom . For example, the binary tree in the figure below , The right view is { 1, 2, 3, 4, 5 }, The left view is { 1, 6, 7, 8, 5 }.

So let's first build a tree through the middle order traversal sequence and post order traversal sequence of a binary tree , Then you have to output the left and right views of the tree .

Input format ：

The first line of input gives a positive integer  N (≤20), Is the number of nodes in the tree . Then, the middle order traversal and post order traversal sequences of the tree are given in two lines . All key values in the tree are different , Its value is irrelevant , Not more than  int  The scope of the .

Output format ：

The first line outputs the right view , The second line outputs the left view , The format is shown in the example .

sample input ：

8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1

sample output ：

R: 1 2 3 4 5
L: 1 6 7 8 5

#include<bits/stdc++.h>
#define ll long long
#define speed_up ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
struct Node{
	int data;
	Node* left;
	Node* right;
};
typedef Node* Tree;
int n;
int in[40],post[40];
map<int,int>pos;
vector<int>L,R;
Tree build(int il,int ir,int pl,int pr){
	
	Tree root=new(Node);
	root->left=NULL;
	root->right=NULL;
	root->data=post[pr];
	int k=pos[post[pr]];
	int size=k-il;
	if(il<k){
		root->left=build(il,k-1,pl,pl+size-1);
	}
	if(ir>k){
		root->right=build(k+1,ir,pl+size,pr-1);
	}
	return root;
}
void bfs(Tree root){
	queue<Tree>p;
	p.push(root);
	while(p.size()){
		int n=p.size();
		for(int i=0;i<n;i++){// The only detail , Find the leftmost and rightmost 
			Tree t=p.front();
			p.pop();
			if(i==0)L.push_back(t->data);
			if(i==n-1)R.push_back(t->data);
			if(t->left)p.push(t->left);
			if(t->right)p.push(t->right);
		}
	}
}
int main(){
	speed_up
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>in[i];
		pos[in[i]]=i;
	}
	for(int i=0;i<n;i++){
		cin>>post[i];
	}
	Tree B=build(0,n-1,0,n-1);
	bfs(B);
		cout<<"R:";
	for(int i=0;i<R.size();i++)
		cout<<" "<<R[i];
    
	cout<<"\nL:";
	for(int i=0;i<L.size();i++)
		cout<<" "<<L[i];
	

	return 0;
}