aoj

ALDS1_7_D Tree - Reconstruction of a Tree

ALDS1_7_D Tree - Reconstruction of a Tree
Feb. 2, 2020, 1:52 p.m.

目次

問題

解答

 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
int n, pos;
vector<int> in, pre, post;


void rec(int l, int r) {
    if (l >= r) return;
    int root = pre[pos++];
    int m = distance(in.begin(), find(in.begin(), in.end(), root));
    rec(l, m);
    rec(m + 1, r);
    post.push_back(root);
}

void solve() {
    pos = 0;
    rec(0, pre.size());
    int i;
    loop(i, 0, n) {
        if (i) cout << " ";
        cout << post[i];
    }
    cout << endl;
}


int main(void) {
    int x;
    cin >> n;
    loop(i, 0, n) {
        cin >> x;
        pre.push_back(x);
    }

    loop(i, 0, n) {
        cin >> x;
        in.push_back(x);
    }

    solve();
}