acwing1497-树的遍历

本文最后更新于:2021年3月27日 下午

题目

一个二叉树,树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。

输入格式

第一行包含整数 NN,表示二叉树的节点数。

第二行包含 NN 个整数,表示二叉树的后序遍历。

第三行包含 NN 个整数,表示二叉树的中序遍历。

输出格式

输出一行 NN 个整数,表示二叉树的层序遍历。

数据范围

1≤N≤301≤N≤30

输入样例:

1
2
3
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

1
4 1 6 3 5 7 2

代码

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

const int N = 40;

int n;
int postorder[N], inorder[N];
unordered_map<int, int> l, r, pos;

int build(int il, int ir, int pl, int pr)
{
int root = postorder[pr];
int k = pos[root];
if (il < k) l[root] = build(il, k - 1, pl, pl + k - 1 - il);
if (ir > k) r[root] = build(k + 1, ir, pl + k - 1 - il + 1, pr - 1);
return root;
}

void bfs(int root)
{
queue<int> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
cout << t << ' ';
if (l.count(t)) q.push(l[t]);
if (r.count(t)) q.push(r[t]);
}
}


int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> postorder[i];
for (int i = 0; i < n; i ++ )
{
cin >> inorder[i];
pos[inorder[i]] = i;
}
int root = build(0, n - 1, 0, n - 1);
bfs(root);
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!