백준 5639 이진 검색 트리

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

5639번: 이진 검색 트리

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> tree;

void postorder(int s, int e){

    if (s >= e) {
        return;
    }
    if (s == e - 1) {
        cout << tree[s] << "\n";
        return;
    }
    int cur = s + 1;
    while (cur < e) {
        if (tree[s] < tree[cur]) {
            break;
        }
        cur++;
    }

    postorder(s + 1, cur);
    postorder(cur, e);
    cout << tree[s] << "\n";

}

int main() {

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

    int n;

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

    postorder(0, tree.size());

    return 0;
}

 

입력 순서대로 배열에 추가한다. 

preorder는 루트->좌->우, postorder는 좌->우->루트 순이므로 다음과 같이 처리한다.

 

  1. s는 루트 노드이다. 루트 다음의 노드를 cur로 잡고(이는 좌측 child 노드이다) cur을 하나씩 증가시켜가면서 우측 child 노드를 찾는다.(이진 검색트리의 정의에 의해 s보다 더 큰 값이 처음 나오는 쪽이 우측 child 노드이다)

  2. 찾았다면 postorder의 정의에 따라 좌측 노드(s+1, cur), 우측 노드(cur, e), root(print(tree[s])) 순으로 재귀를 돌린다.

 

 

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

 

  이 문제를 풀면서 입력의 개수가 주어지지 않는 문제에 입력을 받는 법을 몰랐다(혹은 까먹었던 걸수도 있다).

위의 코드는 입력값이 유효한 값이 들어오는 동안만 입력을 받는 코드이다.