2022 团体程序设计天梯赛 模拟赛 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>
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;							//在后序遍历中找出根节点的值 
	while(p[ps]!=c)ps++;						//在中序遍历中找出根节点的值 
	x->x=c;										//将根节点赋值
	if(ps!=pl){									//如果有左子树 
		t* sl=(t*)malloc(sizeof(t));			//新建节点 
		sl->l=NULL;								//左子节点设置为空
		sl->r=NULL;								//右子节点设置为空
		sl->f=x->f+1;							//记录新建节点的层数 
		x->l=sl;								//将新建节点连接到根节点 
		op(pl,ps-1,ql,ql+ps-pl-1,p,q,sl);		//递归操作 
	}
	if(ps!=pr){									//如果有右子树，过程类似 
		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));					//根节点 
	s->l=NULL;									//根节点左子节点设置为空 
	s->r=NULL;									//根节点右子节点设置为空 
	s->f=0;										//根节点层次设置为0 
	cin>>n;
	p=(int*)malloc(sizeof(int)*n);				//中序数组 
	q=(int*)malloc(sizeof(int)*n);				//后序数组 
	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);						//建树 
	vector<t*> v;								//层序访问 
	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;								//右视图，逆序遍历，借助栈 
	int rv[n]={0};								//右视图访问数组，记录已访问层次 
	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};								//左视图访问数组，直接输出 
	for(int i=0;i<v.size();i++){
		if(!lv[v[i]->f]){
			lv[v[i]->f]=1;
			cout<<' '<<v[i]->x;
		}
	}
	return 0;
}