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

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

풀이

입력값은 전위 순회 결과이므로 루트-왼쪽-오른쪽 순서이다. 그리고 이 트리는 이진 검색 트리이다.
즉, 첫번째 값은 루트이고, 루트보다 작은 왼쪽 서브트리의 값들이 나열되고, 루트보다 큰 오른쪽 값들이 나열된다.

루트보다 큰 값을 가지는 최초 노드의 인덱스를 greater에 저장하고, greater 이전과 이후로 나누어 후위 순회를 실행하였다.

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> tree;

void postOrder(int left, int right) {
    if(left > right) return;
    
    int root = tree[left];
    
    int greater = left+1;
    for(int i=left+1; i<=right; i++) {
        if(tree[i] > root) {
            greater = i;
            break;
        }
    }
    
    postOrder(left+1, greater-1);
    postOrder(greater, right);
    cout << root << "\n";
    
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int value;
    while(cin >> value) {
        tree.push_back(value);
    }
    
    postOrder(0, tree.size()-1);
    
    return 0;
}