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

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

5639번: 이진 검색 트리

문제

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

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

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

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

입력

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

출력

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

---

preorder 순서로 저장된 배열은

[자신][자신보다 작은 수][자신 보다 큰 수]의 순으로 출력이 된다.

 

postorder로 출력을 하려면

[자신보다 작은 수][자신보다 큰 수][자신]을 출력해야 한다.

#include <iostream>

using namespace std;

int node[10001];
int idx = 0,input;

void postOrder(int s , int e){
    int mid;

    if(s >= e)
        return;
    else if(s == e - 1){
        cout << node[s] << "\n";
        return;
    }
    for(mid = s + 1; mid < e ; mid++){
        if(node[mid] > node[s])
            break;
    }
    postOrder(s+1,mid);
    postOrder(mid,e);
    cout << node[s] << "\n";
}

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

    while(cin >> input){
        node[idx++] = input;
    }
    postOrder(0,idx);
}

---

전위순회, 후위순회의 순회방법은 익숙한데 실제로 문제를 풀려고 하니 마땅한 자료구조가 생각나지 않았다. 수업시간에 배울 때는 링크드 리스트를 활용하였기 때문에 메모리 풀 기법을 사용할까 했지만 사용한 지 오래되어 쉽게 구현이 되지 않았다. 하지만 이런 문제에서 메모리풀을 사용할 것 같지 않다는 생각이 들었고 찾아보았더니 그대로 배열에 저장해도 재귀 만으로 풀 수가 있었다. 조금만 생각해도 간단한 문제였을 것 같은데 생각을 하지 않았나 보다. 알고 있는 개념이라고 문제를 바로 풀기는 쉽지 않은가 보다! 그래도 이렇게 풀었으니 다음번에는 틀리지 않아야겠다!