二叉树的遍历

题目描述

二叉树是最经典的一种树形结构，其中每个节点最多有两个子节点，我们把他们称为左右儿子。而二叉树的深度优先遍历是确定二叉树形态的一种重要手段。

现在给你一颗以节点1为根的二叉树，请你输出他的先序遍历，中序遍历和后序遍历。

输入格式

第一行为一个整数 $n$，表示树的大小。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，代表第 $i$ 个节点的左儿子和右儿子编号(如果该节点没有左右儿子则为-1)。

数据范围： $1 \le n \le 10^5$

输出格式

输出三行，分别表示这颗二叉树的先序遍历，中序遍历和后序遍历。

样例 #1

样例输入 #1

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

样例输出 #1

1 2 3 4 5 6 
3 2 4 1 5 6 
3 4 2 6 5 1

提示

样例表示的二叉树如下图所示：