tree

木の復元

木の復元
Feb. 2, 2020, 1:51 p.m.

目次

木の復元

先行順と中間順それぞれで訪れたノードの順序が分かれば、それを見比べて木を復元することができる.
どちらか一方だけでは木の形は確定しない.

以下は木を復元して、後行順ででノードベクターに格納する例.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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 reconstruction() {
    pos = 0;
    rec(0, pre.size());
}