[트리 단계] 백준 5639번 이진 검색 트리

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

50 30 24 5 28 45 98 52 60에서 

50이 루트고 50 기준으로

50보다 작은 수인 30, 24 , 5 ,28 ,45 은 왼쪽 서브트리

큰 수인 98 , 52, 60은 오른쪽 서브트리가 된다.

 

각각에 대해서 도 왼쪽 서브트리 30,24,5,28에서 30이 루트가 되고 24,5,28은 왼쪽 45는 오른쪽이 된다.

계속 분리해 가면서 최종 단계에서 출력하면 됨.

후위 탐색이므로 

왼쪽 탐색, 오른쪽 탐색, 출력 순으로 구현하면 된다.

#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);
}