Romantic silhouette of L2-3 of 2022 group programming ladder Simulation Competition (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

It's a test of basic skills

#include <bits/stdc++.h>
using namespace std;
struct t{
	t *l,*r;
	int x,f;
};
void op(int pl,int pr,int ql,int qr,int *p,int *q,t* x){
	int c=q[qr],ps=pl;							// Find the value of the root node in the subsequent traversal  
	while(p[ps]!=c)ps++;						// Find the value of the root node in the middle order traversal  
	x->x=c;										// Assign a value to the root node 
	if(ps!=pl){									// If I have a left subtree  
		t* sl=(t*)malloc(sizeof(t));			// The new node  
		sl->l=NULL;								// The left child node is set to null 
		sl->r=NULL;								// The right child node is set to null 
		sl->f=x->f+1;							// Record the number of layers of the new node  
		x->l=sl;								// Connect the new node to the root node  
		op(pl,ps-1,ql,ql+ps-pl-1,p,q,sl);		// Recursive operation  
	}
	if(ps!=pr){									// If I have a right subtree , The process is similar to  
		t* sr=(t*)malloc(sizeof(t));
		sr->l=NULL;
		sr->r=NULL;
		sr->f=x->f+1;
		x->r=sr;
		op(ps+1,pr,ql+ps-pl,qr-1,p,q,sr); 
	}
}
int main(void){
	int n,*p,*q;
	t* s=(t*)malloc(sizeof(t));					// The root node  
	s->l=NULL;									// The left child node of the root node is set to null  
	s->r=NULL;									// The right child node of the root node is set to null  
	s->f=0;										// The root node hierarchy is set to 0 
	cin>>n;
	p=(int*)malloc(sizeof(int)*n);				// Middle order array  
	q=(int*)malloc(sizeof(int)*n);				// Post order array  
	for(int i=0;i<n;i++)cin>>p[i];
	for(int i=0;i<n;i++)cin>>q[i];
	op(0,n-1,0,n-1,p,q,s);						// Build up trees  
	vector<t*> v;								// Sequence access  
	v.push_back(s);
	for(int i=0;i<n;i++){
		if(v[i]->l)v.push_back(v[i]->l);
		if(v[i]->r)v.push_back(v[i]->r);
	} 
	stack<int> rp;								// Right side view , Traversal in reverse order , Aided stack  
	int rv[n]={0};								// The right view accesses the array , Record accessed hierarchy  
	for(int i=v.size()-1;i>=0;i--){
		if(!rv[v[i]->f]){
			rv[v[i]->f]=1;
			rp.push(v[i]->x);
		}
	}
	cout<<"R:";
	while(!rp.empty()){
		cout<<' '<<rp.top();
		rp.pop();
	}
	cout<<endl<<"L:";
	int lv[n]={0};								// The left view accesses the array , Direct output  
	for(int i=0;i<v.size();i++){
		if(!lv[v[i]->f]){
			lv[v[i]->f]=1;
			cout<<' '<<v[i]->x;
		}
	}
	return 0;
}