“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。
520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……
我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。
于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。
输入格式：
输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。
输出格式：
第一行输出右视图，第二行输出左视图，格式如样例所示。
输入样例：
1
2
3
| 8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
|
输出样例：
1
2
| R: 1 2 3 4 5
L: 1 6 7 8 5
|
思路：
根据树的中序和后序遍历序列建立树，得到树的层次遍历序列，则左视图L为每层的第一个数，右视图R为每层的最后一个数字
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
using namespace std;
#define MAX 22
int N,i,in[MAX],post[MAX];
vector<int> v[MAX];
int mx;
void build(int inL,int inR,int postL,int postR,int level)
{
if(inL>inR||postL>postR)
return ;
int index=0;
mx=max(mx,level);
while(in[index+inL]!=post[postR])
index++;
v[level].push_back(post[postR]);
build(inL,inL+index-1,postL,postL+index-1,level+1);
build(inL+index+1,inR,postL+index,postR-1,level+1);
}
int main()
{
cin>>N;
for(i=0;i<N;i++)
cin>>in[i];
for(i=0;i<N;i++)
cin>>post[i];
build(0,N-1,0,N-1,0);
cout<<"R:";
for(i=0;i<=mx;i++)
cout<<" "<<v[i].back();
cout<<endl<<"L:";
for(i=0;i<=mx;i++)
cout<<" "<<v[i][0];
return 0;
}
|
