题目描述

从键盘读入 $n$ 个不相同的整数，以每个整数作为结点的值，来创建一棵二叉排序树，假设读入的第 $1$ 个点是这棵树的根结点。

请求出这棵二叉排序树中序和后续遍历的结果？

输入

共两行，第一行为整数 $n$ ；

第二行为 $n$ 个不重复的整数 $a_i$ 。（ $0 < n < 10^5$ ， $1≤a_i≤10^5$ ，本题中 $a_i$ 为随机生成的数值）

输出

共两行，第一行为中序遍历的结果，第二行为后序遍历的结果，同一行的输出用空格隔开。

样例

8
23 45 12 6 7 89 13 47

6 7 12 13 23 45 47 89 
7 6 13 12 47 89 45 23

来源

二叉树