[C++] 백준 2263번 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

풀이

이 문제를 해결하기 위해서는 각 순회의 특징을 알아야한다. postorder의 맨 마지막은 항상 루트이다.
inorder는 루트를 기준으로 좌우로 나뉜다.
이를 이용해 루트를 구한후 inorder에서 좌우 노드들을 얻어내고 다시 postorder에서 좌우 노드들의 루트를 구한다. 이를 반복하여 문제를 해결할 수 있다.
pos는 inorder배열내의 숫자의 위치를 기록한 배열이다. 함수 실행마다 root의 위치를 직접 찾으면 시간낭비가 너무 심하기때문에 미리 구해놓는편이 좋다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#define endl '\n'

using namespace std;

int n;
int inorder[100000];
int postorder[100000];
int pos[100001];

void solve(int is, int ie, int ps, int pe){
  if (is > ie || ps > pe) return;

  int root = postorder[pe];
  cout << root << " ";

  int ir = pos[root]; 

  solve(is, ir-1, ps, ps+ir-is-1);
  solve(ir+1, ie, ps+ir-is, pe-1);
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    cin >> inorder[i];
  }

  for (int i=0; i<n; i++){
    cin >> postorder[i];
  }

  for (int i=0; i<n; i++)
    pos[inorder[i]] = i;

  solve(0,n-1,0,n-1);
}