时间限制： 2.0 秒

空间限制： 512 MB

题目描述

给定一个 $n$ 个节点的二叉树，节点编号为 $1\sim n$，其中 $1$ 号节点为根。

请你依次求出它的前序、中序、后序遍历。

输入格式

从标准输入读入数据。

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

接下来 $n$ 行，每行两个整数，分别表示转化的二叉树当中， $i$ 号节点的左子节点和右子节点的编号。特殊地，若其左/右子节点不存在，则对应位置为 $0$。

输出格式

输出到标准输出。

输出三行，每行 $n$ 个数字，每个数字为二叉树的节点编号，相邻数字之间用空格隔开。第一行为前序遍历，第二行为中序遍历，第三行为后序遍历。

7
2 7
4 0
0 0
0 3
0 0
0 5
6 0

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

样例 1 解释

二叉树结构如图：

子任务

对于所有数据，保证 $n\le 10^6$。

本题无数据梯度，需要通过全部数据获得所有分数。

提示

Chap 05 二叉树 5.4.1 递归式遍历

本题输入量较大，请采用效率较高的读入方式。

来源

洛谷 B3642