[C++] 이진 검색 트리 (백준 5639번)

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

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> a;

void post(int s, int e) {
    if (s >= e) return;

    int idx = e;
    for (int i = s + 1; i < e; i++) {
        if (a[i] > a[s]) {
            idx = i;
            break;
        }
    }
    
    post(s + 1, idx);
    post(idx, e);
    cout << a[s] << '\n';
}

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

    int x;
    while (cin >> x) {
        a.push_back(x);
    }

    int n = a.size();
    post(0, n);
}

 

이 문제는 트리 구조를 만들어서 뭔갈 한다기 보다는 어떻게 하면 전위 순회를 통해 트리 구조를 파악하고, 그걸 또 후위 순회로 어떻게 바꿀까를 생각하면 도움이 된다. 

전위 순회 결과에서 맨 위의 값은 가운데 값이고, 그 값을 기준으로 그보다 작은 수들은 왼쪽 서브트리를 이루고 그 보다 큰 수들은 오른쪽 서브트리를 이룬다. 

이 과정을 재귀적으로 반복하면 이렇게 된다. 각 서브트리 안에서 또 다시 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있는 것이다. 각 트리에서 왼쪽, 오른쪽, 루트 순서로 출력하면 그것이 바로 후위 순회인 것이다.

(AC)