L2-3 浪漫侧影 (25 分)

“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。

520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……

我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。

于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。

输入格式：

输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。

输出格式：

第一行输出右视图，第二行输出左视图，格式如样例所示。

输入样例：

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

输出样例：

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++){//唯一的细节，找最左和最右
			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;
}