题目描述

给定一棵二叉树的后序遍历序列和中序遍历序列，树中每个节点有一个互不相同的编号。请输出这棵树的先序遍历序列。

保证两个序列恰好对应同一棵二叉树。

输入格式

第一行一个整数 $n$，表示节点个数。

第二行 $n$ 个整数，表示后序遍历序列（左子树 → 右子树 → 根）。

第三行 $n$ 个整数，表示中序遍历序列（左子树 → 根 → 右子树）。

所有编号构成 $1\sim n$ 的一个排列。

输出格式

一行 $n$ 个整数，用空格分隔，表示先序遍历序列（根 → 左子树 → 右子树）。

样例输入1

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

样例输出1

1 2 4 5 8 3 6 7

样例输入2

5
5 4 3 2 1
1 2 3 4 5

样例输出2

1 2 3 4 5

数据范围与约定

• $1\le n\le 200000$

提示

后序序列的最后一个数一定是当前子树的根。在中序序列中找到根的位置后，根左边是左子树、右边是右子树，左右子树就可以递归处理。

如果每次都在中序序列里从头到尾线性寻找根，总复杂度是 $O(n^2)$（想想退化成链的树），无法通过满规模数据。可以先预处理每个编号在中序序列中的位置（编号是 $1\sim n$ 的排列，用数组即可 $O(1)$ 定位），使整道题做到 $O(n)$。

另外，$n$ 很大且树退化成链时，递归深度可能达到 $200000$ 而导致栈溢出。可以用显式栈模拟递归：每弹出一段区间就先输出根，再依次把右子树区间、左子树区间压栈，出栈顺序天然就是先序。