题目描述

《修剪二叉树》

给定一棵二叉树，修剪只包含0的子树。 输出修剪后的二叉树的中序和后序序列。

输入格式

第一行是一个正整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n， 根结点为 1， n <= 10 。接下来有 n 行， 依次对应二叉树的结点1~n。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右）儿子。

输出格式

输出2行，修剪后的二叉树的中序和后序序列各一行。如果整棵树都被修剪（变成空树），遍历序列输出“NULL”。

样例

输入样例 1

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

输出样例 1

5 3 12 6 7 
5 3 7 6 12

输入样例 2

3
0 2 3
0 -1 -1
0 -1 -1

输出样例 2

NULL
NULL

输入样例 3

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

输出样例 3

1 2 
2 1

输入样例 4

3
5 2 3
1 -1 -1
2 -1 -1

输出样例 4

1 5 2 
1 2 5