Description

给定一棵二叉树。分别输出其先序遍历，中序遍历，后序遍历。

Input Format

第一行一个整数 $n$ 表示结点个数。

接下来 $n$ 行。第 $i$ 行两个整数分别表示 $i$ 号结点的左右儿子，若为 $0$ 表示不存在该子结点。

Output Format

共三行。

第一行 $n$ 个整数表示二叉树的先序遍历。

第二行 $n$ 个整数表示二叉树的中序遍历。

第三行 $n$ 个整数表示二叉树的后序遍历。

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

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

Hint

$1≤n≤10^3$

Source

模板