#P3205. 排序二叉树

排序二叉树

Description

排序二叉树是一棵有顺序,且没有重复元素的二叉树。

对每个节点而言:

  1. 如果左子树不为空,则左子树上的所有节点的权值都小于该节点的权值。
  2. 如果右子树不为空,则右子树上的所有节点的权值都大于该节点的权值。

6523c8277afee7dde9f8b56e14a06377f3919b84.png

上图为一棵排序二叉树。相信你已经发现,将排序二叉树上的节点的权值按照中序遍历顺序排列成的序列,一定是严格单调递增的。

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

Source

信奥星OJ http://127.0.0.1