[백준 4256] 트리 (C++ 풀이)

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

4256번: 트리

풀이

preorder와 inorder의 결과를 이용하여 범위 내에서 중심이 되는 지점(좌우로 나뉘는 기점)을 찾고, 이를 기준으로 left/right로 범위를 나누어서(분할정복) 재귀함수를 호출하며 postorder의 결과를 출력합니다.

 

void post_order(int start, int end, int pos){
    for (int i = start; i < end; ++i) {
        if(v_in[i] == v_pre[pos]){
            post_order(start, i, pos + 1); // 트리의 left 서브트리 탐색
            post_order(i+1, end, pos + 1 + i - start); // 트리의 right 서브트리 탐색
            cout << v_pre[pos] << ' '; // 현재 위치의 root 숫자 출력
        }
    }
}

 

우선 preorder의 첫번째 숫자는 root number인 것을 알 수 있습니다.

이 root number의 위치를 inorder에서 찾으면, 그 위치를 기준으로 트리는 좌/우로 나뉘게 됩니다. 

(트리의 서브트리 또한 트리 자료구조라는 점을 이용)

 

따라서 inorder에서의 위치를 기준으로 좌/우로 배열을 나누어 재귀함수를 호출합니다. 

그리고 새로운 root number의 위치를 1 증가 시킵니다.(기존 3 위치에서 6의 위치로)

 

root를 기준으로 트리의 왼쪽을 모두 전개하면 다음과 같습니다.

마찬가지로 오른쪽 트리도 모두 전개해줍니다.

 

따라서 전체 소스코드는 다음과 같습니다.

#include <vector>
#include <iostream>

using namespace std;

int T;
int N;
vector<int> v_pre;
vector<int> v_in;


void post_order(int start, int end, int pos){
    for (int i = start; i < end; ++i) {
        if(v_in[i] == v_pre[pos]){
            post_order(start, i, pos + 1);
            post_order(i+1, end, pos + 1 + i - start);
            cout << v_pre[pos] << ' ';
        }
    }
}

void solve(){
    int root_idx = 0;
    post_order(root_idx, N, 0);
    cout << endl;
}


int main() {
    cin >> T;

    for (int i = 0; i < T; ++i) {
        cin >> N;
        v_pre = vector<int>(N);
        v_in = vector<int>(N);

        for (int j = 0; j < N; ++j) {
            cin >> v_pre[j];
        }
        for (int j = 0; j < N; ++j) {
            cin >> v_in[j];
        }
        solve();
    }
}