1669_建树并迭代遍历二叉树

按指令建立二叉树，然后遍历二叉树。

指令格式如下：

• 0 id name ：表示建立根节点，编号为id，姓名为name。

• 1 father id name ：表示为父节点father增加左孩子，编号为id，姓名为name。如果父节点father已经有左孩子，则新增节点替换原左孩子，原左孩子成为新节点的左孩子。

• 2 father id name ：表示为父节点father增加右孩子，编号为id，姓名为name。如果父节点father已经有右孩子，则新增节点替换原右孩子，原右孩子成为新节点的右孩子。

第一行是一个正整数n，表示树节点总数。n < 50000

接下来n行，每行是一条指令，格式和意义如上所述。

题目保证每个id唯一。

保证指令0是首条指令，并只出现一次。题目保证每一条指令的 father 节点在树中已存在。

首先采用迭代先序遍历方式，输出n行：二叉树的先序遍历序列，每行是该节点的id和name 。然后输出一个空行。

然后采用迭代中序遍历方式，输出n行：二叉树的中序遍历序列，每行是该节点的id和name 。然后输出一个空行。

最后采用迭代后序遍历方式，输出n行：二叉树的后序遍历序列，每行是该节点的id和name 。然后输出一个空行。

当然，如果没用迭代方式的遍历，判cheat并封号。

9
0 0 lvxhtmhduuf
1 0 1 axekqtixysyqkmrg
1 0 2 bps
2 2 3 tewtjzogltqbrmq
2 3 4 yymybxz
1 0 5 x
1 3 6 vyqkxlij
1 0 7 tvxlczod
1 4 8 cee

0 lvxhtmhduuf
7 tvxlczod
5 x
2 bps
1 axekqtixysyqkmrg
3 tewtjzogltqbrmq
6 vyqkxlij
4 yymybxz
8 cee

1 axekqtixysyqkmrg
2 bps
6 vyqkxlij
3 tewtjzogltqbrmq
8 cee
4 yymybxz
5 x
7 tvxlczod
0 lvxhtmhduuf

1 axekqtixysyqkmrg
6 vyqkxlij
8 cee
4 yymybxz
3 tewtjzogltqbrmq
2 bps
5 x
7 tvxlczod
0 lvxhtmhduuf