[백준] 5639 이진 검색 트리

전위순회를 주고 후위순회한 결과를 출력하는 문제다

트리를 직접 만들어도 되지만 그러면 귀찮다

푸는방법은 전위,후위순회를 할 때 방문하는 노드를 생각해보면된다

전위순회한 결과에서 첫번째 노드는 항상 루트다

그리고 두번째 노드부터 루트보다 큰노드가 나오기 전까지는 왼쪽서브트리

큰노드부터 마지막까진 오른쪽 서브트리다

그럼 범위를 쪼개가며 재귀로 타고 들어가서

왼쪽 오른쪽 순서로 들어가며 루트를 출력해주면 원하는 답을 얻을 수 있다!

그림을 그려서 생각해보면 쉽다!

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int arr[10010], n;
 
void go(int l, int r) {
    if (l > r) return;
 
    int root = l;
    int s = l, e = r;
    while (arr[s] >= arr[root]) s++;
    while (arr[e] > arr[root]) e--;
    go(s, e);
    go(e + 1, r);
    printf("%d\n", arr[root]);
    
}
int main() {
    int x;
    while (scanf(" %d", &x) != -1) arr[n++] = x;
    go(0, n - 1);
}