2.28模拟题 problem2 进击的二叉查找树

题目描述
给定1~N的两个排列,使用这两个排列分别构建两棵二叉查找树(也就是通过往一棵空树中依次插入序列元素的构建方式)。如果这两棵二叉查找树完全相同,那么输出YES;否则输出NO。之后,输出第一个排列对应的二叉查找树的后序序列、层序序列。

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

第一行1个正整数N(1<=N<=30),表示二叉查找树中的结点个数。

接下来两行,代表1~N的两个排列。

输出
如果两个排列代表的二叉查找树完全相同,那么输出一行YES,否则输出一行NO。

接下来两行分别输出第一个排列对应的二叉查找树的后序序列、层序序列,整数之间用空格隔开。

每行末尾不允许有多余的空格。

样例输入
5
4 2 1 3 5
4 5 2 3 1
样例输出
YES
1 3 2 5 4
4 2 5 1 3

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 40;
struct node{
int data;
int lchild;
int rchild;
}Node[maxn * 2];
int nodenum = 0;
int n;
vector<int> post1, post2, lev1;
int newNode(int x){
Node[nodenum].data = x;
Node[nodenum].lchild = -1;
Node[nodenum].rchild = -1;
return nodenum++;
}
void insert(int &root, int x){
if (root == -1) {
root = newNode(x);
return;
}
if (x < Node[root].data) {
insert(Node[root].lchild, x);
}
if (x > Node[root].data) {
insert(Node[root].rchild, x);
}
}
int createTree(int arr[]){
int root = -1;
for (int i = 0; i < n; i++) {
insert(root, arr[i]);
}
return root;
}
void post(int root, vector<int>& vi){
if (root == -1) {
return;
}
post(Node[root].lchild, vi);
post(Node[root].rchild, vi);
vi.push_back(Node[root].data);
}
void lev(int root, vector<int>& vi){
queue<int> q;
q.push(root);
while (!q.empty()) {
int now = q.front();
q.pop();
vi.push_back(Node[now].data);
if (Node[now].lchild != -1) q.push(Node[now].lchild);
if (Node[now].rchild != -1) q.push(Node[now].rchild);
}
}
int main() {
int str1[maxn], str2[maxn];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &str1[i]);
}
int root1 = createTree(str1);
for (int i = 0; i < n; i++) {
scanf("%d", &str2[i]);
}
int root2 = createTree(str2);
post(root1, post1);
post(root2, post2);
lev(root1, lev1);
if (post1 == post2) {
printf("YES\n");
}else{
printf("NO\n");
}
for (int i = 0; i < n; i++) {
printf("%d", post1[i]);
if(i < n - 1)printf(" ");
else printf("\n");
}
for (int i = 0; i < n; i++) {
printf("%d", lev1[i]);
if(i < n - 1)printf(" ");
else printf("\n");
}

return 0;
}