[Link] https://www.acmicpc.net/problem/4256
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
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define endl "\n"
typedef long long ll;
const int INF = 987654321;
const int MAX = 100;
struct Node {
int left = -1;
int right = -1;
};
int n;
vector<int> pre;
vector<int> mid;
vector<int> mid_idx_vec;
vector<Node> nodes;
int idx = 0;
int patch(int mid_left, int mid_right) {
if(mid_left > mid_right) return -1;
int node_val = pre[idx++];
int mid_idx = mid_idx_vec[node_val];
nodes[node_val].left = patch(mid_left, mid_idx - 1);
nodes[node_val].right = patch(mid_idx + 1, mid_right);
return node_val;
}
void post_order(int idx) {
if(nodes[idx].left != -1) post_order(nodes[idx].left);
if(nodes[idx].right != -1) post_order(nodes[idx].right);
cout << idx << " ";
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--) {
int n; cin >> n;
pre.clear();
mid.clear();
mid_idx_vec.resize(n+1);
nodes.clear();
idx = 0;
for0(i, n) { int in; cin >> in; pre.push_back(in); }
for0(i, n) { int in; cin >> in; mid.push_back(in); mid_idx_vec[in] = i; }
for(int i = 0; i <= n; i++) nodes.push_back(Node());
patch(0, n - 1);
post_order(pre[0]);
cout << endl;
}
return 0;
}