日々精進

aikoと旅行とプログラミング

【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に至っては存在すら知らなかった. 猛省.