PAT-A 1127 ZigZagging on a Tree (30)

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Problem: PAT-A 1127 ZigZagging on a 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 inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification

For each test case, print the zigzagging sequence of the tree in a line. 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

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output

1

1 11 5 8 17 12 20 15

Analysis

  通过中序和后序序列构造二叉树，然后按层输出。与普通层次遍历不同的是，偶数层（0 层开始）正序输出，奇数层倒序输出。使用 DFS 或 BFS 遍历整个树，记录各个结点的层号，将数据按层存放于数组。输出时逐层输出，根据层号判断使用正序或倒序输出。

Code

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

#include <bits/stdc++.h>
using namespace std;
const int mxN = 75;

int G[mxN][3], post[mxN], in[mxN];
vector<int> res[mxN];  // 按层存放数据

int build_tree(int pL, int pR, int iL, int iR) {
    if (pL > pR) return -1;
    int k = iL;
    while (k <= iR) {
        if (in[k] == post[pR]) break;
        k++;
    }
    int numleft = k - iL;
    G[post[pR]][0] = build_tree(pL, pL + numleft - 1, iL, k - 1);
    G[post[pR]][1] = build_tree(pL + numleft, pR - 1, k + 1, iR);
    return post[pR];
}

// 根据各结点的层号，按层存放数据
int mxL = -1;
void get_res(int r, int lyr) {
    mxL = max(mxL, lyr);  // 获取层数
    res[lyr].push_back(r);
    if (G[r][0] > -1) get_res(G[r][0], lyr + 1);
    if (G[r][1] > -1) get_res(G[r][1], lyr + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> in[i];
    for (int i = 0; i < N; i++) cin >> post[i];
    int root = build_tree(0, N - 1, 0, N - 1);
    get_res(root, 0);

    // 0, 2, 4 ... 倒序输出
    // 1, 3, 5 ... 正序输出
    int cnt = 0;
    for (int i = 0; i <= mxL; i++) {
        int len = res[i].size();
        if (i & 1) {
            for (int j = 0; j < len; j++) {
                cout << " " << res[i][j];
            }
        } else {
            for (int j = len - 1; j >= 0; j--) {
                if (cnt++) cout << " ";
                cout << res[i][j];
            }
        }
    }
}

Tsukkomi

  巩固了一遍中序 + 后序序列生成二叉树，还行吧。一开始数组开了 35，交上去居然段错误？？题目标的 N <= 30，但结点序号范围并不在 [1, N]。