Skip to content

1127 ZigZagging on a Tree

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 16 KB
  • 时间限制: 400 ms
  • 内存限制: 64 MB

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.

zigzag.jpg

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N (\le30), 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 

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

Sample Output 

1 11 5 8 17 12 20 15

Solution

#include <bits/stdc++.h>
using namespace std;
const int N = 1100;
int n, rt, a[N], b[N], c[N], deep[N];
vector<vector<int>> vec;
struct E {
    int son[2];
    E() {
        son[0] = son[1] = 0;
    }
} e[N];
int gao(int al, int ar, int bl, int br) {
    if (al > ar || bl > br)
        return 0;
    int rt = a[ar], pos = -1;
    for (int i = bl; i <= br; ++i) {
        if (b[i] == rt) {
            pos = i;
            break;
        }
    }
    if (al >= ar)
        return rt;
    int lsze = pos - bl;
    e[rt].son[0] = gao(al, al + lsze - 1, bl, pos - 1);
    e[rt].son[1] = gao(al + lsze, ar - 1, pos + 1, br);
    return rt;
}

void bfs(int S) {
    queue<int> que;
    que.push(S);
    deep[S] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vec[deep[u]].push_back(c[u]);
        int v = e[u].son[0];
        if (v) {
            deep[v] = deep[u] + 1;
            que.push(v);
        }
        v = e[u].son[1];
        if (v) {
            deep[v] = deep[u] + 1;
            que.push(v);
        }
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        memset(e, 0, sizeof e);
        memset(deep, 0, sizeof deep);
        vec.clear();
        vec.resize(n + 35);
        for (int i = 1; i <= n; ++i) scanf("%d", b + i), c[i] = b[i];
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        sort(c + 1, c + 1 + n);
        for (int i = 1; i <= n; ++i) {
            a[i] = lower_bound(c + 1, c + 1 + n, a[i]) - c;
            b[i] = lower_bound(c + 1, c + 1 + n, b[i]) - c;
        }
        int rt = gao(1, n, 1, n);
        bfs(rt);
        vector<int> res;
        for (int i = 1; i <= n + 30; ++i) {
            if (vec[i].empty())
                break;
            if (i & 1) {
                reverse(vec[i].begin(), vec[i].end());
            }
            for (auto &it : vec[i]) res.push_back(it);
        }
        assert(res.size() == n);
        for (int i = 0; i < n; ++i) printf("%d%c", res[i], " \n"[i == n - 1]);
    }
    return 0;
}
Last update: May 4, 2022
Back to top