Problem 1010. -- 还原二叉树

1010: 还原二叉树

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 17  Solved: 4
[Submit][Status][Web Board]

Description

给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。

Input

每个输入文件中一组数据。

第一行一个正整数N1<=N<=30),代表二叉树的结点个数(结点编号为1~N)。接下来两行,每行N个正整数,分别代表二叉树的层序遍历序列和中序遍历序列。数据保证序列中1~N的每个数出现且只出现一次。

Output

输出两行,每行N个正整数,分别代表二叉树的先序遍历序列和后序遍历序列。每行末尾不输出额外的空格。

Sample Input

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

Sample Output

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

HINT

Source

[Submit][Status]