题目

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$ ( $\le 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:

1
2
3

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

1

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最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#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;
}