【AOJ ALDS1_7】D: Tree - Reconstruction of a Tree
問題
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge
方針
- inorderを先頭から見ていったとき, その値をcとする.
- そのcの位置をpreorderの中から探し, その値をmとする.
- prem[m]より左側の値はcを根とする木の左部分木, 右側は右部分木となる.
- それを再帰的に定義していく.
例
- n = 5
- pre = {1, 2, 3, 4, 5}
- in = {3, 2, 4, 1, 5}
最初の根は1(pre[0])となり, 左部分木は[3, 2, 4], 右部分木は[5]となる.
左部分木の[3, 2, 4]のうち根は2(pre[1])となり, 左部分木は[3], 右部分木は[4]である.
左部分木が終わったので根が1の木の右部分木となるが, 要素数が1なのでそのまま終了となり木が完成する.
コード
#include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define pb push_back using namespace std; vector<int> pre, in, ans; int n; int pos; void solve(int l, int r){ if(l - r >= 0) return; int root = pre[pos]; pos++; int d = distance(in.begin(), find(in.begin(), in.end(), root)); solve(l, d); solve(d+1, r); ans.pb(root); } signed main(){ cin >> n; int m; rep(i,n){ cin >> m; pre.pb(m); } rep(i,n){ cin >> m; in.pb(m); } solve(0, pre.size()); cout << ans[0]; REP(i,1, n){ cout << " " << ans[i]; } cout << "\n"; }
全く問題とは関係ないことだが, 初めてdistanceとfindを使った. distanceに至っては存在すら知らなかった. 猛省.