文理学院程序设计在线练习


中序遍历二叉树

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 62   Accepted Submission(s): 23
Problem Description

给定一棵二叉树,要求输出二叉树的深度以及中序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。

Input

输入数据分为多组,第一行是测试数据的组数T。然后接T组测试。
对于每组测试,首先是一个正整数n,代表即将给出的二叉树的节点总数(当然,其中可能包含虚节点)。结点编号均为正整数,且各不相同。
二叉树的构造按照完全二叉树的顺序给出(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以 0代替)

Output

分两行分别输出中序遍历二叉树得到的序列(结点之间保留一空格)以及每棵二叉树的深度。

Sample Input
2
1 1
4 1 4 0 2
Sample Output
1
1
2 4 1
3