【AIZU ONLINE JUDGE】木の復元の問題を解いてみた - プログラミング原人の進化論

木の復元の問題です。木の巡回の応用問題となってます。

木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

例

まず、例を見て解き方を考察します。
先行順巡回で P = {1, 2, 3, 4, 5}、中間順巡回で I = {3, 2, 4, 1, 5} という順でノードが訪問される場合を考えます。

（１）

f:id:programgenjin:20190223161255p:plain

Pより、根は１です。さらに、Iをみると、1の左側に{3, 2, 4}、右側に{5}があることがわかります。 Iは中間順巡回を表しているので、左部分木と右部分木に属するノードが特定できます。

（２）

f:id:programgenjin:20190223193711p:plain

（１）の右部分木はノードが５だけなので、部分木の構造は自明です。Pの２番目の要素が２であることから、左部分木は２を根とする部分木であることがわかります。さらに、Iから、２の左側に{3}、右側に{4}があることがわかります。

（３）

f:id:programgenjin:20190223161728p:plain

属しているノードの数が１つだけであることから、ノード３、４は確定します。

解答

再帰的に部分木をたどっていく過程で、部分木に属するノードに対応するIの範囲を狭めていきますが、Iの範囲を表現するためにインデックスright, leftを導入します。rightは該当範囲の先頭、leftは末尾+1です。

f:id:programgenjin:20190223214135j:plain

解答例はこちら。

#include<iostream>
#include<vector>
using namespace std;

int Pre[100];  // 先行順巡回で得られるノード
int In[100];   // 中間順巡回で得られるノード
vector<int> Post;  // 後行順にノードを格納
int pos;      // 部分木のrootのPreでの位置

// 木を復元する
void reconstruction(int left, int right) {
  if (left >= right) return;  // 終了条件
  
  int root, root_pos;

  root = Pre[pos++];  // Preの順番にノードに訪問

  // rootのInでの位置を探す
  root_pos = left;
  for (int i = left; i < right; i++) {
    if (In[i] == root) {
      root_pos = i;
    }
  }
  
  reconstruction(left, root_pos);       // 左部分木
  reconstruction(root_pos + 1, right);  // 右部分木

  Post.push_back(root);  // 後行順にノードを格納
}


int main() {
  int i, n, pos;
  
  cin >> n;  
  for (i = 0; i < n; i++) cin >> Pre[i];
  for (i = 0; i < n; i++) cin >> In[i];

  // 木の復元
  pos = 0;
  reconstruction(0, n);

  // 出力
  for (i = 0; i < n; i++) {
    if (i > 0) cout << " ";
    cout << Post[i];
  }
  cout << endl;

  return 0;
}