3.1模拟题 problem4 上帝视角

题目描述
给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列,并给出从右往左、从右上往左下、从上往下分别能看到的结点个数。注意,此处均把二叉树的每条边都设置为等长,角度为45度,因此结点可能在视觉上重叠。所谓从右往左看是指,对同一层的结点,右边的结点会挡住左边的结点,这样同一层结点就只能看到最右边的那一个;同样的,从右上往左下看是指,右上角的结点会挡住左下角45度的结点;从上往下看是指,对同一竖直位置来说,只能看到最上方的结点。

例如对下图来说,从右往左能看到3个结点,从右上往左下能看到3个结点,从上往下能看到5个结点。

请输入图片描述

输入
每个输入文件中一组数据。

第一行一个正整数N(1<=N<=30),代表二叉树的结点个数(结点编号为1~N)。

接下来两行,每行N个正整数,分别代表二叉树的层序遍历序列和中序遍历序列。数据保证序列中1~N的每个数出现且只出现一次。

输出
先输出两行,每行N个正整数,分别代表二叉树的先序遍历序列和后序遍历序列。

接下来分三行输出从右往左、从右上往左下、从上往下分别能看到的结点个数。

每行末尾均不允许输出多余的空格。

样例输入
7
1 2 3 4 5 6 7
4 2 5 1 6 3 7
样例输出
1 2 4 5 3 6 7
4 5 2 6 7 3 1
3
3
5

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>
#include <ctype.h>
#include <iostream>
using namespace std;
int in[50], la[50];
int n;
vector<int> layervec, prevec, postvec;
struct node{
int data,layer;
node *left, *right;
node(node *_left = NULL, node *_right = NULL ){
left = _left;//初始化
right = _right;//初始化
}
};
node* createTree(vector<int> layer, int inL, int inR){
if (layer.size() == 0) {//层次遍历为空,返回空地址
return NULL;
}
node* root = new node;
root->data = layer[0];//层次向量中第一个为根节点
int k;
for (k = inL; k <= inR; k++) {
if (layer[0] == in[k]) {//在中序遍历中找到根节点
break;
}
}
vector<int> layerLeft;
vector<int> layerRight;
for (int i = 1; i < layer.size(); i++) {//在层次向量中枚举根节点左侧
bool isLeft = false;
for (int j = inL; j < k; j++) {
if (layer[i] == in[j]) {
isLeft = true;
}
}
if (isLeft) {//找到一个按顺序放入,顺序在前的为根节点
layerLeft.push_back(layer[i]);
}else{
layerRight.push_back(layer[i]);
}
}
root->left = createTree(layerLeft, inL, k - 1);
root->right = createTree(layerRight, k + 1, inR);
return root;
}
void preOrder(node *root, vector<int> &vi){
if (root == NULL) {
return;
}
vi.push_back(root->data);
preOrder(root->left, vi);
preOrder(root->right, vi);
}
void postOrder(node *root, vector<int> &vi){
if (root == NULL) {
return;
}
postOrder(root->left, vi);
postOrder(root->right, vi);
vi.push_back(root->data);
}
int maxlep = 0;
void dfs(node* root, int ldep){
maxlep = max(maxlep, ldep);
if (root == NULL) {
return;
}
if(root->left)dfs(root->left, ldep);
if(root->right)dfs(root->right, ldep + 1);
return;
}
int minleaf = 0, maxleaf = 0;
void dfs1(node* root, int ldep){
minleaf = min(minleaf, ldep);
maxleaf = max(maxleaf, ldep);
if (root == NULL) {
return;
}
if(root->left)dfs1(root->left, ldep - 1);
if(root->right)dfs1(root->right, ldep + 1);
return;
}
int layerOrder(node*root){//返回层数
queue<node*> q;
q.push(root);
root->layer = 1;
int maxlayer = 0;
while (!q.empty()) {
node* now = q.front();
q.pop();
maxlayer = max(now->layer, maxlayer);
if (now->left != NULL) {
now->left->layer = now->layer + 1;
q.push(now->left);
}
if (now->right != NULL) {
now->right->layer = now->layer + 1;
q.push(now->right);
}

}
return maxlayer;
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i++) {//layer
scanf("%d", &la[i]);
layervec.push_back(la[i]);//入向量
}
for (int i = 0; i < n; i++) {//in
scanf("%d", &in[i]);
}
node *root = new node;
root = createTree(layervec, 0, n - 1);
preOrder(root,prevec);
postOrder(root,postvec);
for (int i = 0; i < n; i++) {
printf("%d",prevec[i]);
if (i < n - 1) {
printf(" ");
}else printf("\n");
}
for (int i = 0; i < n; i++) {
printf("%d",postvec[i]);
if (i < n - 1) {
printf(" ");
}else printf("\n");
}
dfs(root, 0);//从右上往左下看
dfs1(root, 0);//从上往下看
printf("%d\n", layerOrder(root));
printf("%d\n", maxlep + 1);
printf("%d\n", abs(minleaf) + maxleaf + 1);
return 0;
}