#P3205. 排序二叉树
排序二叉树
Description
排序二叉树是一棵有顺序,且没有重复元素的二叉树。
对每个节点而言:
- 如果左子树不为空,则左子树上的所有节点的权值都小于该节点的权值。
- 如果右子树不为空,则右子树上的所有节点的权值都大于该节点的权值。
上图为一棵排序二叉树。相信你已经发现,将排序二叉树上的节点的权值按照中序遍历顺序排列成的序列,一定是严格单调递增的。
Input Format
第一行为一个整数n,表示树的结点个数。
第二行为n个数,第i个数表示第i个加入排序二叉树的结点的权值,两两不同且都为正整数。
Output Format
总共n行。对于第i行,第一个数是表示第i个加入排序二叉树的结点的权值,第二个数是它左儿子的权值,第三个数是它右儿子的权值,当然有可能没有,如果没有,则输出-1。
7
5 3 1 4 7 6 8
5 3 7
3 1 4
1 -1 -1
4 -1 -1
7 6 8
6 -1 -1
8 -1 -1