Problem B: 平衡二叉树的操作

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：2 Solved：1

Description

给定一前序二叉树的数据，请构造根节点为 root 的二叉树，将这棵树转化为平衡二叉搜索树，删除INT（最大节点值/2）并插入INT（最大节点/3)后输出该树序列。

Input

输入为一棵树的先序遍历序列，遇到不存在的子节点用0表示。输入的结尾为-1。

Output

输出为一棵树的中序遍历序列。

Sample Input Copy 

4 2 1 0 0 3 0 0 6 5 0 0 0 -1

Sample Output Copy 

1 2 2 4 5 6

HINT

树的深度最多为19层。