### 题目
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
**Input Specification:**
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
**Output Specification:**
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
**Sample Input:**
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
**Sample Output:**
4 1 6 3 5 7 2
==**说白了就是,给你一棵二叉树的后序遍历结果和中序遍历结果,让你输出这棵二叉树的层序遍历结果。**==
### 题解:
我们应该都接触过由中序遍历和先序遍历得到后序遍历,或者由中序遍历和后序遍历得到先序遍历,其实只要你根据给出的两个序列重构出这棵二叉树,层序遍历也就得到了。
但重构二叉树需要自己创建二叉树的数据结构,还要造一棵树出来,其中指针操作又容易出错,我不想创建树可以吗?可以的!题目只是让我输出最后的遍历结果,又不是让我得到一棵树,我只需要巧妙的调整一下代码就能利用一个`map`得到层序遍历的结果([柳婼大神nb](https://www.liuchuo.net/archives/2100))
但不管怎么样,都得先解决一个问题,就是利用中序序列和后序序列怎么得到二叉树呢?这里我简单说一下吧,相信大多数人都会这个操作的。
**给个例子:**
中序遍历: A D E F G H M Z
后序遍历: A E F D H Z M G
画树求法:
第一步,根据后序遍历的特点,我们知道**后序遍历最后一个结点即为根结点**,即根结点为G。
第二步,观察**中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。**
第三步,根据后序遍历(左右中)的特点,后序遍历中,**根G的左边的节点M必然是它的右子树HMZ的根。**
第四步,右子树HMZ有三个节点,**根G往左移三个位置后D必然是它的左子树的根**。
第五步,观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下:
1 确定根,确定左子树,确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 返回或者打印当前根。
**层序遍历**
那我们一般是怎么是层序遍历,`宽度优先遍历`,层序其实也就是按顺序,一般都是用一个`队列`,队列中保存的始终是一整层的姐弟啊,对于每层每个节点,访问自己,把左右孩子加入队列,==【保证了访问的先后顺序】==
我们这里采用键值对`map`的形式保存,**值:节点值,键:层序遍历下它实际的访问序号(下标)**,对于每个节点,假如编号是`i`,那么它的`左孩子编号是2 * i,右孩子编号是 2*i+1`,**因为键值的大小关系,map会自动按其顺序排序,相当于保证了访问的先后顺序**,这样我们最后直接按顺序输出整个map的值,就实现了队列的功能。
但是因为 我们的序列是数组,下标是从0开始的,所以为了避免 2 * 0 = 0节点值覆盖,我们`左孩子编号是 2*i+1,右孩子编号是 2*i+2`,当然你可以选择让根节点编号是1,就不会有这个问题。
### 代码实现
```cpp
#include
#include
#include

PAT 1020 Tree Traversals (25分) 解读