A1020 Tree Traversals
摘要
Title: A1020 Tree Traversals
Tag: 树的遍历
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
A1020 Tree Traversals
-
题意
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
-
思路
后序和中序出层序
-
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-01-05 13:52:39
* @FilePath: \GPLT\A1020\A1020.cpp
* @LastEditTime: 2023-01-05 14:12:33
*/
using namespace std;
const int N = 50;
int inod[N], postod[N], l[N], r[N];
int n;
unordered_map<int, int> order;
int bulid(int il, int ir, int pl, int pr)
{
int root = postod[pr];
int k = order[root];
// 诀窍：
// 1. 判断条件就是，中序遍历的两端点大小关系
// 2. 后序遍历就从后往前看，用统一的标准，如 (ir - k - 1), 写的对的话，两句的长度是一样的
if (ir >= k + 1)
r[root] = bulid(k + 1, ir, pr - 1 - (ir - k - 1), pr - 1);
if (il <= k - 1)
l[root] = bulid(il, k - 1, pl, pr - 1 - (ir - k - 1) - 1);
return root;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> postod[i];
for (int i = 0; i < n; ++i)
{
cin >> inod[i];
order[inod[i]] = i;
}
int root = bulid(0, n - 1, 0, n - 1);
queue<int> q;
q.push(root);
vector<int> ans;
while (!q.empty())
{
auto t = q.front();
q.pop();
ans.push_back(t);
if (l[t])
q.push(l[t]);
if (r[t])
q.push(r[t]);
}
for (int i = 0; i < SZ(ans); ++i)
cout << ans[i] << " "[i == SZ(ans) - 1];
return 0;
}