陈远龙精品编程（信奥赛） 助力信奥赛学子取得优秀的成绩

题目描述

给出一棵二叉树的先序遍历和中序遍历，请你编程构造出这棵二叉树，输出该二叉树的后序遍历结果，同时你还需要完成另一项任务。

该二叉树的每个节点的值都是一个不重复的正整数，如下图的二叉树：

先序序列：1 2 4 7 3 5 8 9 6

中序序列：4 7 2 1 8 5 9 3 6

该二叉树对应的后序序列是： 7 4 2 8 9 5 6 3 1

你需要完成的另一个任务是，找出这棵二叉树中从每个叶子节点到根节点所有节点值的和最小的那个叶子，如果和相同，则以叶子节点的值小的为最终结果

比如上图中：

叶子节点到根节点的路径有：

1. 1 2 4 7，路径和为：14
2. 1 3 5 8，路径和为：17
3. 1 3 5 9，路径和为：18
4. 1 3 6，路径和为：10

其中叶子节点到根节点的路径和最小的是1 3 6这条路径，对应的叶子节点是6

输入格式

第1行，1个正整数n，代表二叉树中一共有n个节点

第2行，二叉树的先序遍历结果，每个整数使用一个空格分隔

第3行，二叉树的中序遍历结果，每个整数使用一个空格分隔

输出格式

第1行，二叉树的后序遍历结果，每个整数使用一个空格分隔

第2行，最小路径和的叶子节点的值

输入输出样例

输入样例	输出样例
9 1 2 4 7 3 5 8 9 6 4 7 2 1 8 5 9 3 6	7 4 2 8 9 5 6 3 1 6

数据范围与提示

对于100%的数据满足：1 <= n <= 1000，二叉树里每个节点里的值为1 - 1000，不会出现重复的值

本题数据量较大，可能需要用到C++加速读写

测试点数目

共10个测试点，每个测试点10分

时间与内存限制

每个测试点时间：1000ms（1.0s），内存：256MiB

输入输出模式

本OJ支持两种输入输出模式