二叉树的遍历

题目概述

给定一棵共有 n 个结点的二叉树（根结点编号为 1）。 对每个结点 i 给出它的左右子结点编号（若不存在则为 0）。 请建立这棵二叉树，并依次输出它的前序、中序、后序遍历序列。

输入格式

• 第一行：一个整数 n（结点数，\(1 \le n \le 10^6\)）。

• 接下来 n 行：第 i 行包含两个整数 l r，分别表示结点 i 的左、右子结点编号。

  • l = 0 表示无左子结点；r = 0 表示无右子结点。
  • 叶子结点的输入为 0 0。

约定：结点编号均在 [1, n] 内；根结点编号为 1。

输出格式

输出三行，每行 n 个整数，数字之间以一个空格分隔：

1. 第一行：二叉树的前序遍历序列。
2. 第二行：二叉树的中序遍历序列。
3. 第三行：二叉树的后序遍历序列。

样例

输入

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

小提示

• 数据量可达 10^6，请注意时间与空间效率。
• 若语言递归栈深度有限，建议使用迭代遍历或 Morris 遍历以避免栈溢出。