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

문제

접근 방법

이진 검색 트리에서 왼쪽 노드는 작고 오른쪽 노드는 크다는 점을 활용하면 된다.
전위 순회의 결과이기에 다음 입력이 현재 값보다 낮은 값이면 왼쪽 서브 노드라는 것을 알 수 있다.
오른쪽 서브 노드의 값은 지금 노드의 값보다 큰 값인데 가장 처음 만난 큰 값이 오른쪽 서브 노드의 값이다. (전위 순회한 결과이기 때문이다)

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> tree;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int node;
    while (cin >> node)
    {
        tree.push_back(node);
    }
}
void recur(int start, int end)
{
    if (start >= end) // 범위를 벗어나는 경우
    {
        return;
    }

    int choice = start + 1, num = tree[start];
    for (; choice < end; ++choice)
    {
        if (tree[choice] > num) // 현재 값보다 큰 경우
        {
            num = tree[choice];
            break;
        }
    }

    recur(start + 1, choice); // 좌측
    recur(choice, end);       // 우측
    cout << tree[start] << "\n";
}
int main()
{
    input();
    recur(0, tree.size());
    return 0;
}

풀이

이진 검색 트리의 성질을 활용하면 된다.
오른쪽 서브 노드를 찾은 뒤 재귀 함수로 왼쪽과 오른쪽으로 범위를 나누어 탐색하면 된다.
왼쪽과 오른쪽으로 탐색을 완료한 후 출력을 하면 후위 순회한 결과가 출력될 것이다.