[백준 2263] 트리의 순회

문제

www.acmicpc.net/problem/2263

 

알고리즘

재귀

 

풀이

트리의 인오더, 포스트오더가 주어질 때, 프리오더를 출력하는 문제입니다.

 

포스트오더는 배치가 왼쪽 서브트리 포스트오더 출력 + 오른쪽 서브트리 포스트오더 출력 + 루트 입니다. 즉 맨 오른쪽 값이 루트임을 알 수 있습니다. 인오더의 배치는 왼쪽 서브트리 인오더 출력 + 루트 + 오른쪽 서브트리 인오더 출력입니다. 포스트오더에서 루트를 파악했다면 인오더에서 해당 루트의 위치를 찾아 왼쪽 서브트리와 오른쪽 서브트리를 나누어줍니다. 인오더와 포스트오더의 서브트리의 크기는 일치하므로 인오더에서 찾은 서브트리크기를 통해 포스트오더의 구간을 나누어 재귀호출하면 풀 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e5;

int N;
int in[MAXN];
int post[MAXN];
int rev[MAXN];

void solve(int il, int ir, int pl, int pr) {
    if (il > ir || pl > pr)
        return;
    int r = post[pr];
    cout << r + 1 << ' ';
    int idx = rev[r];

    solve(il, idx - 1, pl, pl + idx - il - 1);
    solve(idx + 1, ir, pl + idx - il, pr - 1);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        cin >> in[i];
        rev[--in[i]] = i;
    }
    rep(i, N) {
        cin >> post[i];
        post[i]--;
    }
    solve(0, N - 1, 0, N - 1);
    return 0;
}