二叉树

---

描述

给定一个1到n的排列，按顺序依次插入到一棵二叉排序树中，请你将这棵二叉树前序遍历和后序遍历输出。

前序遍历的定义

后序遍历的定义

输入

第一行一个整数n。

接下来一行表示为n个整数，代表1到n的一个排列。

输出

输出所建成的二叉树的前序遍历和后序遍历。

输入样例

10
2 6 9 3 5 7 10 8 4 1


输出样例

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


限制

对于50%的数据，1 ≤ n ≤ 100；

对于100%的数据，1 ≤ n ≤ 100000。

保证建成的树的高度不超过50。

时间：2 sec

空间：256 MB

提示

[二叉树的操作基本都是递归操作，只要想想如何在一个节点上判断是朝着左孩子走还是朝着右孩子走就行了。]

另外，为了帮助大家完成题目，我们提供了只包含了输入输出功能的程序模板，也提供了含有算法的大部分实现细节的程序。

你可以根据自己的实际情况，在这些程序的基础上进行作答，或不参考这些程序，这将与你的得分无关。

这些程序可以从【这里】下载。