题目描述

给定一个二叉树，按前序、中序和后序三种遍历方式输出二叉树的结点编号。

输入格式

第1行输入结点的个数n；n<=20
接下来n行按照下述格式输入各结点的信息，每个结点占1行： id    left    right。id为结点编号，left为左子结点编号， right为右子结点编号。不存在子结点时left(right)为－1。0<=id<=20 。

输出格式

第1行输出“Preorder”；
第2行按前序遍历的顺序输出结点编号，以空格隔开；
第3行输出“Inorder”；
第4行按中序遍历的顺序输出结点编号，以空格隔开；
第5行输出“Postorder”；
第6行按后序遍历的顺序输出结点编号，以空格隔开。

样例数据

input

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

output

Preorder
0 1 2 3 4 5 6 7 8
Inorder
2 1 3 0 6 5 7 4 8
Postorder
2 3 1 6 7 5 8 4 0