BOJ 2263 트리의 순회

문제

https://www.acmicpc.net/problem/2263

이진트리에서 중위순회 + 전위순회 or 후위순회 의 결과가 주어졌을 때 나머지 하나를 출력하는 문제이다.

 

풀이

분할정복 분야에서 꽤 유명한 문제이다.

전위순회 or 후위순회로는 해당하는 트리에서의 루트를 구할 수 있고, 

중위순회로는 구한 루트를 기준으로 왼쪽, 오른쪽 서브트리를 구할 수 있다.

 

이때 전위순회 or 후위순회 에서는 i번째 노드가 순회된 순서를 저장해놔야 루트를 O(1) 만에 구할 수 있다.

 

시간 복잡도 : $O(N)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 100000

int n;
int in[MAXN+10], post[MAXN+10], key[MAXN+10];

vector<int> ans;

void restore(int s, int e, int now)
{
    if(s>e || now==0) return;

    ans.push_back(post[now]);
    int pos=key[post[now]];

    now--;

    restore(s, pos-1, now-(e-pos));
    restore(pos+1, e, now);
}

int main()
{
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=1; i<=n; i++) { scanf("%d", &in[i]); key[in[i]]=i; }
    for(i=1; i<=n; i++) scanf("%d", &post[i]);

    restore(1, n, n);
    for(i=0; i<ans.size(); i++) printf("%d ", ans[i]);

    return 0;
}