#CSES1702. 树的遍历

树的遍历

题目背景

翻译自 CSES-1702 题。

题目描述

有三种常见的方式来遍历二叉树的节点:

  • 先序遍历:首先访问根节点,然后遍历左子树,最后遍历右子树。
  • 中序遍历:首先遍历左子树,然后访问根节点,最后遍历右子树。
  • 后序遍历:首先遍历左子树,然后遍历右子树,最后访问根节点。

现在有一棵包含 nn 个节点的二叉树,节点的标签是唯一的。你已经给定了树的先序遍历和中序遍历,你的任务是求出树的后序遍历。

输入格式

第一行包含一个整数 nn,表示节点的数量。节点编号为 1,2,,n1, 2, \dots, n

接下来有两行描述树的先序遍历和中序遍历。每行包含 nn 个整数。

输出格式

输出树的后序遍历。

样例

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

说明/提示

1n1051 \leq n \leq 10^5