백준 5639 이진 검색 트리

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

5639번: 이진 검색 트리

이진 검색트리의 순회를 활용하여 문제를 풀어보겠습니다. 

 

이 문제의 입력은 이진 검색 트리를 전위순회한 값으로 주어지고 있습니다. 전위 순회는 root, 왼쪽 노드, 오른쪽 노드 순으로 진행이 됩니다. 이진 검색트리의 왼쪽 노드는 작은 값들만 존재하기 때문에 이점을 잘 이용해야 합니다. 

 

그래서 root 보다 큰 값의 인덱스를 찾은 다음 left, right 부분을 나누어서 분할 정복을 해주면 쉽게 해결할 수 있습니다. 여기서 해당 index를 찾기 위해서 이진탐색을 이용한 upper_bound를 사용했습니다. 

 

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int size;
int arr[100002];
void input();
void getPostorder(int start, int end);

int main(){
	input();
	getPostorder(0, size);
}

void input(){
	int num;
	while(scanf("%d", &num) != -1){
		arr[size++] = num; 
	}
}


void getPostorder(int start, int end){
	if(start >= end)return;
	int upperIndex = distance(arr, upper_bound(arr+start+1, arr + end, arr[start]));

	getPostorder(start+1, upperIndex);	
	getPostorder(upperIndex, end);
	printf("%d\n", arr[start]);
}

 

위 문제에서 또 문제의 의도와 다르게 직접 이진검색트리를 구현하여 문제를 해결할 수도 있습니다. 트리를 구성한 후 후위 순회를 돌려서 결과를 출력하면 됩니다.