我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。
题目
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 (
), 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
思路
大体思路
题目输入两种方法遍历的结果：后序遍历（postorder）和中序遍历（inorder），让我们
给出层序遍历（level order）的结果。
其实相当于要求我们复原整个树的结果，那么怎么从后序遍历和中序遍历中得到这棵树的
结构呢？我们可以先看这两种遍历是怎么输出的：
- 后序遍历：L R N
- 中序遍历：L N R
L代表左子树，R代表右子树，N代表当前节点。我们则可以采取这样的策略：
- 从后序遍历的最后一个节点得到根节点
- 在中序遍历中找到该根节点
- 分别界定两个列表中左子树L和右子树R的子数组
- 对左子树和右子树分别进行1-3步骤
思路上属于分而治之的方法，虽然最简单的实现就是递归，但是在这里貌似不适合。因为
我们最终要进行层序遍历，那么使用递归的话，复原树的结构顺序就是前序了，无法直接
实现题目要求。所以我使用了队列（queue）来实现，其实层序遍历一般就是用队列来实
现的。
数据结构
仅在这说明一下我的数据结构，以便理解我的代码。为了表示根节点的信息，我使用了三
个变量：
- post: 指向后序遍历子数组的指针
- in: 指向中序遍历子数组的指针
- length: 数组长度（两者相同）
所以并没有直接保存节点的信息，因为很好获得，就是后序遍历最后一个即是。
代码
最新代码@github，欢迎交流
#include <stdio.h>
#define QLEN 15
#define CNODE 31
typedef struct node{
int *post, *in, length;
}node;
typedef struct queue{
node *nodes[QLEN];
int front, rear, count;
}queue;
void enqueue(queue *q, node *n)
{
q->nodes[q->rear] = n;
q->rear = (q->rear == QLEN - 1) ? 0 : q->rear + 1;
q->count++;
}
node *dequeue(queue *q)
{
node *n = q->nodes[q->front];
q->front = (q->front == QLEN - 1) ? 0 : q->front + 1;
q->count--;
return n;
}
int main()
{
int post[CNODE] = {0}, in[CNODE] = {0}, N;
queue q = {0}; /* Initialize to zeros or NULL array */
int root, index, count;
scanf("%d", &N);
for(int i = 0; i < N; i++)
scanf("%d", post + i);
for(int i = 0; i < N; i++)
scanf("%d", in + i);
node nodes[CNODE] = {{post, in, N}}, *p = nodes, *n;
enqueue(&q, p++);
for(count = 0; q.count; count++)
{
n = dequeue(&q);
/* Find root node in post-order, which is the last one */
root = n->post[n->length - 1];
/* Find the root node in in-order */
for(index = 0; index < n->length; index++)
if(n->in[index] == root)
break;
/* The subsequence post/in-order of left child */
p->post = n->post;
p->in = n->in;
p->length = index;
if(p->length != 0) /* left child not NULL */
enqueue(&q, p++);
/* The subsequence post/in-order of right child */
p->post = n->post + index;
p->in = n->in + index + 1;
p->length = n->length - index - 1;
if(p->length != 0) /* right child not NULL */
enqueue(&q, p++);
/* print */
printf("%d%c", root, (count == N - 1) ? '\0' : ' ');
}
return 0;
}
