[백준,c++] 5539번 - 이진 검색 트리

문제

5639번: 이진 검색 트리

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int>v;

void postorder(int start, int end){
    if(start>end) return;
    if(start==end){
        cout<<v[start]<<'\n';
        return;
    }
    
    int root_index = start;
    while(true){
        root_index++;
        if(v[start]<v[root_index]) break;
        if(root_index>end) break;
    }
    
    postorder(start+1, root_index-1);
    postorder(root_index, end);
    cout<<v[start]<<'\n';   // 루트노드 출력
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int inp;
    while(cin>>inp){
        v.push_back(inp);
    }
    
    postorder(0, v.size()-1);
    
}

 

풀이

이진트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 출력하는 문제입니다.

풀이 아이디어는 다음과 같습니다. 문제의 예제 입력과 같은 다음 입력 있을 때, 각각 Root, Left, Right는 다음과 같습니다.

50 30 24 5 28 45 98 52 60 

빨간색: Root, 파란색: Left, 초록색: Right 

그 이유는 일단 Root 노드는 50일 이고, 30부터 Left 노드인데 Root보다 처음으로 큰 값이 나오면 해당 Node는 Right 노드의 시작점이 됩니다.

따라서 해당 아이디어 방식으로 루트를 기점으로 좌우 양쪽으로 분할하여 또다시 처음과 같은 방법을 반복하게 되면 리프 노드에 도달하게 되는데 그때 리프 노드를 출력하는 방식으로 구현하면 해결할 수 있습니다.