[백준] 5639.cpp : 이진 검색 트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

---

• 노드 값들을 주고 후위 순회대로 출력하는 것이 아닌, 전위 순회 출력을 입력으로 주기 때문에, 노드를 만드는 것이 까다롭다.
• 이진 트리의 속성 중 왼쪽 서브트리들은 모두 작은 값, 오른쪽 서브트리들은 모두 큰 값이라는 조건이 있다.
• 위 조건을 활용하여 해당 노드에서의 왼쪽, 오른쪽 구역을 나눌 수 있다.
• 각자 구역은 또다시 특정 노드의 이진트리가 되는데, 이 때 특정 노드값을 알아내면 재귀호출이 가능하다.
• 전위 순회를 입력으로 주었기 때문에, 특정 노드의 양쪽 서브트리를 구할 때, 바로 다음 입력값이 왼쪽 노드, 처음으로 나오는 큰 값이 오른쪽 노드가 된다.
• 처음에 입력값을 받으면서 입력 종료 시점에 대해서 처리해줄 때 주의해야 한다.

---

#include <iostream>
#include <vector>

using namespace std;

vector<int> data;

void post(int begin, int end)               // begin 은 노드 시작점, end 는 마지막 점 (포함하지 않음)
{
    if(begin >= end)                        // 인덱스 초과 시 그냥 종료
    {
        return;
    }
    if(begin == end - 1)                    // 마지막 노드일 시 출력 후 종료
    {
        cout << data[begin] << '\n';
        return;
    }
    int idx;
    for(idx = begin ; idx < end ; idx++)    // 피봇 idx 를 설정 
    {                                       // 양쪽 서브트리를 나눠주는 값으로 지정 (처음으로 나오는 오른쪽 노드값)
        if(data[idx] > data[begin]) break;
    }
    post(begin + 1, idx);                   // 왼쪽 서브트리 재귀 호출
    post(idx, end);                         // 오른쪽 서브트리 재귀 호출
    cout << data[begin] << '\n';            // 노드값 출력
}

int main(void)
{
    int temp;
    do
    {
        cin >> temp;
        data.push_back(temp);
    } while(getc(stdin) == '\n');                           // 개행이 입력될때마다 값 하나씩 입력해서 data 에 집어넣음
    
    if(data[data.size() - 1] == data[data.size() - 2])      // 입력값이 종료될 때 개행문자가 들어간 뒤 종료되면, getc(stdin) 에서 참으로 확인하여 temp 를 한 번 더 넣게 된다.
    {
        data.pop_back();                                    // 만약 뒤의 두개 값이 같은 값이라면 하나를 지워주는 작업
    }

    post(0, data.size());
}