[백준 2263 - C++] 트리의 순회 : 분할 정복

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

2263번: 트리의 순회

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1 

3

1 2 3

1 3 2

예제 출력 1 

2 1 3

 

풀이

이번학기에 자료구조 재수강을 하고 있는데 이번주에 수업한 내용이 인오더 포스트오더 프리오더 였어서 되게 편하게 풀었다

 

인오더, 포스트오더, 프리오더는 위의 그림 같은 순서로 출력이 된다.

포스트 오더를 이용해서 쉽게 루트 노드를 구할 수 있고, 이 루트 노드가 인오더에서 몇번째 오는지 확인해서 왼쪽과 오른쪽을 나눌 수 있다.

이를 이용해서 왼쪽과 오른쪽을 나누면서 재귀를 호출하면된다.

이때 프리오더는 루트, 왼, 오 의 순서로 출력되기 때문에 재귀를 호출할 때마다 루트만 계속 출력 하면 된다.

 

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int in[100001];         //inorder저장
int post[100001];       //postorder저장
int in_temp[100001];    //inorder의 root 쉽게 찾기 위해 사용, 숫자에 대한 위치 저장

void sol(int in_s, int in_f, int post_s, int post_f){
    if(in_s > in_f || post_s > post_f)
        return;
    
    int root = post[post_f];
    int in_Rpos = in_temp[root];
    
    printf("%d ", root);
    sol(in_s, in_Rpos-1, post_s, post_s + (in_Rpos -1 - in_s));
    sol(in_Rpos+1, in_f, post_s + (in_Rpos -1 - in_s)+1, post_f-1);
}

int main (void) {
    int n;
    scanf("%d", &n);
    
    for(int i=0; i<n; i++){
        scanf("%d", &in[i]);
        in_temp[in[i]] = i;
    }
    
    for(int i=0; i<n; i++){
        scanf("%d", &post[i]);
    }
    
    sol(0, n-1, 0, n-1);
}