[C++] 5639: 이진 검색 트리

풀이 방법을 생각해내지 못해서 결국 검색해서 풀었다.

참고로, 입력 종료를 위해 EOF를 입력하려면 맥(리눅스)기준으로 Cmd + D를 입력하면 된다.

🔍 해결 방법

• 전위 순회로 30 24 5 28 45 다음과 같은 트리가 있을 때,
• 30(루트)을 기준으로 더 큰 값이 나오기 전까지는 모두 왼쪽 자식 노드에 해당한다. 30 (24 5 28) 45
• 그리고 나머지는 오른쪽 자식 트리에 해당하게 된다.
• 이 탐색을 재귀적으로 반복해서, 탐색하는 범위가 1개가 되는 경우나 맨 마지막 노드일 경우에 출력해주면 된다.

📇 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

void printPost(int start, int end) {
    if (start >= end) return;
    if (start == end-1) {
        cout << v[start] << '\n';
        return;
    }

    // 현재 노드보다 더 큰 값이 등장하면 그 전까지 왼쪽 자식
    // 그 노드는 오른쪽 자식임 -> 현재보다 더 커지는 인덱스 찾음
    int idx = start + 1;
    while (idx < end) {
        if (v[start] < v[idx]) break;
        idx++;
    }

    // 왼 -> 오 -> 본인 순서로 출력해야 하므로 순서대로 호출
    printPost(start + 1, idx);
    printPost(idx, end);
    cout << v[start] << '\n';
    return;
}

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

    while (cin >> n) {
        v.push_back(n);
    }

    printPost(0, v.size());

    return 0;
}