[BOJ] 5639 - 이진 검색 트리

문제

이진 검색 트리

코드

#include <iostream>

using namespace std;

int arr[10000];

void pre2post(int s, int e){
    if (s >= e) return;
    else if (s == e-1){
        cout << arr[s] << "\n";
        return;
    }
    int idx = s+1;
    for (; idx < e; idx++){
        if (arr[s] < arr[idx]) break;
    }
    pre2post(s+1, idx);
    pre2post(idx, e);
    cout << arr[s] << "\n";
}

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

    int idx = 0, num;
    
    while (cin >> num){
        arr[idx++] = num;
    } 

    pre2post(0, idx);
    return 0;
}

접근

전위 순회는 루트노드, 왼쪽, 오른쪽으로 순회하는 방식이고, 후위 순회는 왼쪽, 오른쪽, 루트 노드로 순회하는 방식이다. 따라서 전위 순서의 첫번째 원소는 루트 노드인 것을 알 수 있고 BST이기 때문에 왼쪽에는 루트보다 작은 값들만 나오는 것도 알고 있다. 이를 통해 루트노드, 왼쪽, 오른쪽 부분으로 나누어서 재귀호출을 통해 해결할 수 있었다.

예시) 전위 순회 : 50(루트) 30 24 5 28 45 (왼쪽) 98 52 60(오른쪽)