Skip to content

1006 Tree Traversals - Hard Version

Statement

Metadata

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

Given the partial results of a binary tree's traversals in in-order, pre-order, and post-order. You are supposed to output the complete results and the level order traversal sequence of the corresponding tree.

Input Specification

Each input file contains one test case. For each case, a positive integer N (\le 100) is given in the first line. Then three lines follow, containing the incomplete in-order, pre-order and post-order traversal sequences, respectively. It is assumed that the tree nodes are numbered from 1 to N and no number is given out of the range. A - represents a missing number.

Output Specification

For each case, print in four lines the complete in-order, pre-order and post-order traversal sequences, together with the level order traversal sequence of the corresponding tree. The numbers must be separated by a space, and there must be no extra space at the beginning or the end of each line. If it is impossible to reconstruct the unique tree from the given information, simply print Impossible.

Sample Input 1 

9
3 - 2 1 7 9 - 4 6
9 - 5 3 2 1 - 6 4
3 1 - - 7 - 6 8 -

Sample Output 1 

3 5 2 1 7 9 8 4 6
9 7 5 3 2 1 8 6 4
3 1 2 5 7 4 6 8 9
9 7 8 5 6 3 2 4 1

Sample Input 2 

3
- - -
- 1 -
1 - -

Sample Output 2 

Impossible

Tutorial

题意：

给出一棵二叉树的中序、前序、后序遍历的残缺序列，问能否唯一的还原出这棵树，如果能，输出中序、前序、后序遍历结果以及层次遍历结果。

结点个数 n (1 \leq n \leq 10^2)。

思路：

  • 判断在三个遍历序列中均为出现的点的个数是否大于 1，如果大于 1, 那么肯定 Impossible，因为这些点的位置肯定可以互换。
  • 我们考虑从中序遍历入手，通过枚举当前子树的中序遍历区间中的根，然后以此分成左右两个子树往下遍历判断合法性。

但是在下面代码中，我认为存在一个问题，就是在枚举根的过程中，我们一旦发现一个合法的根就返回 True，这样是有问题的。

因为可能往下去枚举存在另一个合法的根，那么当前子树的遍历序列就存在多种合法状态，最后构成的树就不是唯一的。

因为多加一个判断，判断当前子序列的合法的根的个数，如果大于 1 个，应该也是Impossible。

但是加上后 WA 了一个点。

举个例子：

3
- - -
1 2 3
3 2 1

它显然存在至少两种状态：

但是下面这份 AC 代码，输出的是有结果的。

替换成注释里的内容后的那份 WA 的代码，输出是 Impossible。

Solution

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) (int(x.size()))
using pII = pair<int, int>;
const int N = 1e2 + 10, INF = 0x3f3f3f3f;
int n, a[N], b[N], c[N], _a[N], _b[N], _c[N], cnt[N];
pII son[N];

int rd() {
    string s;
    cin >> s;
    if (s == "-")
        return 0;
    int num = 0;
    for (auto &ch : s) num = num * 10 + (ch - '0');
    return num;
}

bool dfs(int al, int ar, int bl, int br, int cl, int cr, int &rt) {
    if (al > ar || bl > br || cl > cr)
        return true;
    if (b[bl] != 0 && c[cr] != 0 && b[bl] != c[cr])
        return false;
    for (int i = al; i <= ar; ++i) {
        if (a[i] != 0 && b[bl] != 0 && a[i] != b[bl])
            continue;
        if (a[i] != 0 && c[cr] != 0 && a[i] != c[cr])
            continue;
        int now = max({a[i], b[bl], c[cr]});
        son[i] = pII(0, 0);
        int len = i - al;
        if (dfs(al, i - 1, bl + 1, bl + len, cl, cl + len - 1, son[i].fi) &&
                dfs(i + 1, ar, bl + len + 1, br, cl + len, cr - 1, son[i].se)) {
            _a[i] = _b[bl] = _c[cr] = now;
            rt = i;
            return true;
        }
    }
    return false;
}

void bfs(int st) {
    vector<int> res;
    queue<int> que;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        res.push_back(_a[u]);
        if (son[u].fi)
            que.push(son[u].fi);
        if (son[u].se)
            que.push(son[u].se);
    }
    for (int i = 0; i < SZ(res); ++i) {
        cout << res[i] << " \n"[i == SZ(res) - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    memset(cnt, 0, sizeof cnt);
    int num = n;
    for (auto &arr : {a, b, c}) {
        for (int i = 1; i <= n; ++i) {
            arr[i] = rd();
            if (arr[i] && ++cnt[arr[i]] == 1)
                --num;
        }
    }
    for (int i = 1; i <= n; ++i) {
        _a[i] = a[i];
        _b[i] = b[i];
        _c[i] = c[i];
    }
    int rt = 0;
    if (num > 1 || !dfs(1, n, 1, n, 1, n, rt)) {
        cout << "Impossible\n";
        return 0;
    }
    num = -1;
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) ++cnt[_a[i]];
    for (int i = 1; i <= n; ++i)
        if (cnt[i] == 0)
            num = i;
    for (auto &arr : {_a, _b, _c}) {
        for (int i = 1; i <= n; ++i)
            if (arr[i] == 0)
                arr[i] = num;
        for (int i = 1; i <= n; ++i) {
            cout << arr[i] << " \n"[i == n];
        }
    }
    bfs(rt);
    return 0;
}
Last update: May 4, 2022
Back to top