2.28模拟题 problem3 还原二叉树

题目描述
给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。

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

第一行一个正整数N(1<=N<=30),代表二叉树的结点个数(结点编号为1~N)。接下来两行,每行N个正整数,分别代表二叉树的层序遍历序列和中序遍历序列。数据保证序列中1~N的每个数出现且只出现一次。

输出
输出两行,每行N个正整数,分别代表二叉树的先序遍历序列和后序遍历序列。每行末尾不输出额外的空格。

样例输入
7
3 5 4 2 6 7 1
2 5 3 6 4 7 1
样例输出
3 5 2 4 6 7 1
2 5 6 1 7 4 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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 50;
struct node{
int data;
node *lchild, *rchild;
};
int n, lev[maxn], in[maxn];
vector<int> layer, pre, post;
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->lchild = createTree(layerLeft, inL, k - 1);
root->rchild = 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->lchild, vi);
preOrder(root->rchild, vi);
}
void postOrder(node* root, vector<int> &vi) {
if (root == NULL) {
return;
}
postOrder(root->lchild, vi);
postOrder(root->rchild, vi);
vi.push_back(root->data);
}

int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d", &lev[i]);
layer.push_back(lev[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &in[i]);
}
node* root = NULL;
root = createTree(layer, 0, n - 1);
preOrder(root, pre);
postOrder(root, post);
for (int i = 0; i < n; i++) {
printf("%d", pre[i]);
if (i < n - 1) printf(" ");
else printf("\n");
}
for (int i = 0; i < n; i++) {
printf("%d", post[i]);
if (i < n - 1) printf(" ");
else printf("\n");
}
return 0;
}