← 返回比赛

已结束 GESP巅峰赛#28

← 上一题下一题 →

A6931 | $Alice的神秘二叉树$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一棵结点键值 两两不同 的二叉树的： - 中序遍历 序列 in[1..n] ； - 层序（BFS）遍历 序列 level[1..n] （与中序包含相同的键，顺序为从根到叶、自左到右）。 请你 唯一重构 这棵二叉树，并输出其 先序遍历 序列。

输入格式

- 第一行一个整数 $n$（结点个数）。 - 第二行 $n$ 个两两不同的整数，表示中序序列 in[1..n] 。 - 第三行 $n$ 个整数，表示层序序列 level[1..n] （与中序包含相同的键，并构成同一棵二叉树）。

输出格式

输出一行 $n$ 个整数，为重构后的二叉树的 先序遍历 序列。

输入输出样例

输入 #1

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

输出 #1

1 2 4 5 3 6

输入 #2

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

输出 #2

1 2 4 5 3 6

输入 #3

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

输出 #3

1 2 4 3 5 6

数据范围 - $1 \le n \le 2\times 10^5$； - 键值范围：64 位有符号整数（建议使用 long long）； - 保证 两个序列包含相同的 $n$ 个互不相同的键，并对应某棵合法二叉树。 测试点$n$ 范围1 ～ 6$2 \le n < 500$小规模（约 30%）7 ～ 20$500 \le n \le 2\times 10^5$大规模 样例解释 中序为 [4,2,5,1,6,3]，层序根是 1；在中序上 1 左侧 [4,2,5] 中，层序最早出现的是 2，右侧 [6,3] 中最早出现的是 3。递归划分得到先序 1 2 4 5 3 6。

C++ 编辑器

输入

输出