PAT Advanced 1020. Tree Traversa

我的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代表当前节点。我们则可以采取这样的策略：

1. 从后序遍历的最后一个节点得到根节点
2. 在中序遍历中找到该根节点
3. 分别界定两个列表中左子树L和右子树R的子数组
4. 对左子树和右子树分别进行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;
}