[Gold 4] 5639 이진 검색 트리

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

 

문제에서 입력은 이진 탐색 트리의 전위 순회의 결과로 주어진다.

이때 입력의 종료 조건은 트리의 순회 결과가 모두 들어올때 까지 이다.

따라서 반복의 조건에 입력이 끝날때 까지 받도록 한다.

while(cin>>input){
        tree[idx++] = input;
}

 

전위 순회의 결과를 보면 왼쪽 노드의 값은 루트보다 작으며, 오른쪽 노드의 값은 루트보다 큰 것을 알 수 있다.

따라서 루트보다 작은 것은 왼쪽 노드이며, 루트보다 큰 것은 오른쪽 노드이다.

위 정의는 부모 자식 노드간의 관계에도 성립한다.

따라서 입력 배열의 현재 위치와 그 다음 인덱스의 값이 작으면 왼쪽 노드로 생각하고 크면 오른쪽 노드로 생각하면 된다.

 

 

 

#include <iostream>
using namespace std;

int tree[10000];

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

    int idx = start + 1;
    while(idx < end){
        if(tree[start] < tree[idx])
            break;
        idx++;
    }
    postOrder(start + 1, idx);
    postOrder(idx, end);
    cout<<tree[start]<<'\n';
}

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

    int input;
    int idx = 0;
    while(cin>>input){
        tree[idx++] = input;
    }
    postOrder(0, idx);
}