时间限制： 2.0 秒

空间限制： 40 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.2 迭代版前序遍历 / 5.4.3 迭代版中序遍历 / 5.4.4 迭代版后序遍历

请注意本题非同寻常的空间限制，这意味着我们不允许你使用递归的方式进行遍历。注意到需要迭代处理后序遍历，除了存储左右子节点，还需要存父节点。

此外，C++ 默认的指针类型在本系统中为 64 位，可以使用 int 类型的数组下标（32 位）代替指针的作用，从而节省空间。其他节省空间的方式包括对三种遍历共同使用同一个栈数组等等。

本题输入量较大，请采用效率较高的读入方式。但是由于本题非同寻常的空间限制，请不要使用 fread/fwrite 进行输入输出。

来源

洛谷 B3642，改编