1670_重构二叉树

给出二叉树的先序遍历序列和中序遍历序列，请重构该二叉树，并按层次遍历次序遍历该二叉树。

二叉树可参考如下数据结构：

struct BiTreeNode {
   /// 假设只用到2个数据域
   int  id;  /// 编号
   char  name[20];  /// 名字

   /// lchild 和 rchild 是必要的指针域。
   struct BiTreeNode *lchild;  /// 左孩子指针
   struct BiTreeNode *rchild;  /// 右孩子指针
};

typedef struct BiTreeNode  tNode;   /// 树的节点类型
typedef struct BiTreeNode  *pNode;  /// 树的指针类型

第一行是一个正整数n，表示二叉树的节点数。 0 < n ≤ 1000000 。请注意按层遍历时所需的队列的大小。

接下来n行是该二叉树的先序遍历序列，一个节点一行，分别是id和name。每个id互不相同。0 < |name| < 20

接下来是一个空行。

再接下来n行是该二叉树的中序遍历序列，一个节点一行，分别是id和name。 0 < |name| < 20。id和name就是先序遍历序列的id和name，只不过位置不同。

输出n行，表示该二叉树按层遍历的次序，每个节点一行：id 和 name

11
0 root
1 k
2 gxcoaotwishiye
7 oslbkzhqsaprpe
4 qvcx
8 zckkykuulas
3 kwo
5 aqngjovffuzehq
6 lm
10 pztokybqvph
9 hv

7 oslbkzhqsaprpe
2 gxcoaotwishiye
1 k
4 qvcx
8 zckkykuulas
0 root
6 lm
5 aqngjovffuzehq
10 pztokybqvph
3 kwo
9 hv

0 root
1 k
3 kwo
2 gxcoaotwishiye
4 qvcx
5 aqngjovffuzehq
9 hv
7 oslbkzhqsaprpe
8 zckkykuulas
6 lm
10 pztokybqvph