[백준][C++] 5693번: 이진 검색 트리 <197>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

5639번: 이진 검색 트리

생각의 흐름

사실 이번 문제는 예전에 비슷한 문제를 풀어본 적 있어서, 보자마자 분할 정복(재귀) 방식의 풀이를 떠올렸다.

 

우선 전위 순휘를 나열해보면

50

30

24

5

28

45

98

52

60

전위 순회에서 root노드는 50이 되고, 앞에서 부터 순서대로 읽어을 때,  50 보다 작은값들이 left tree 에 들어있는 부분이다.

반대로 50보다 큰 값들은 right tree에 담겨있는 부분들 이다.

50

30

24

5

28

45

98

52

60

후위 연산은 left, right, root 순이기 때문에 이 순서대로 재귀를 돌려주면 후위 연산의 결과를 출력할 수 있다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

vector<int> vec;

void postOrder(int start, int end){
    if(start >= end){
        return;
    }
    int rootNum = vec[start];

    int i = 0;
    for(i = start+1; i < end; i++){
        if(rootNum < vec[i]){
            break;
        }
    }
    postOrder(start+1, i);
    postOrder(i, end);

    cout << vec[start] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int num;
    while(cin >> num){
        vec.push_back(num);
    }

    postOrder(0, vec.size());

    return 0;
}