[BOJ] 5639 이진 검색 트리

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개 이하이다. 같은 키를 가지는 노드는 없다.

출력

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

---

풀이

전위 순회가 주어졌을 때 후위 순회를 출력하는 문제이다.

1. 주어진 start 인덱스와 end 인덱스를 돌면서 왼쪽 서브트리와 오른쪽 서브트리를 나눠주는 mid_idx 를 구한다.
2. 왼쪽 서브트리를 구하기 위해 start+1과 mid_idx-1을 인자로, 오른쪽 서브트리를 구하기 위해 mid_idx와 end를 인자로 넘기면서 재귀를 돈다.
3. start>end 일 경우는 존재하지 않는 경우이므로 예외 처리를 해주고 start==end일 경우 리프노드이므로 출력만 해준다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v;

void post_order(int start,int end){

    //노드가 존재하지 않는 경우
    if(start>end){
        return;
    }
    
    int root=v[start];
    
    //리프노드일 경우
    if(start==end){
        cout<<root<<endl;
        return;
    }
    
    int mid_idx=start+1;
    for(int i=start;i<=end;i++){
        if(v[i]>root){
            mid_idx=i;
            break;
        }
    }
    //왼쪽 서브트리
    post_order(start+1,mid_idx-1);
    //오른쪽 서브트리
    post_order(mid_idx,end);
    cout<<root<<endl;
}

void input() {
    int n;
    
    while (cin>>n) {    //EOF를 만날때까지 무한 입력
        v.push_back(n);
    }
}

void init() {}

void solution() {
    post_order(0,v.size()-1);
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}