８．５ 木巡回の応用：木の復元

ちょっと間が空いてしまいました。自力で考えたとっkは、すべての木を復元しようとしたのですが、NGでした。ということでこちらは写経となっております。シンプルな再帰とアルゴリズムを思いつくにはどうしたら良いんでしょうねえ。。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static vector<int> preorder(100), inorder(100);

static void inputOrder(vector<int>& order, int num) {
  for (int i = 0; i < num; i++) {
    cin >> order[i];
  }
}

static int current = 0, outIndex = 0;

static int next() {
  int c = preorder[current];
  current++;
  return c;
}

static int find(int c) {
  auto it = find(inorder.begin(), inorder.end(), c); 
  return distance(inorder.begin(), it);
}

static void reconstruction(int l, int r) {
  if (l >= r) {
    return;
  } 
  int c = next();
  int m = find(c);
  reconstruction(l, m);
  reconstruction(m + 1, r);

  if (outIndex != 0) {
    cout << " " << c;
  } else {
    cout << c;
  }
  outIndex++;
}

int main() {
  int n;
  cin >> n;

  inputOrder(preorder, n);
  inputOrder(inorder, n);
  reconstruction(0, n);

  cout << endl;

  return 0;
}