백준 5639번 - 이진 검색 트리 (c++)

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

5639번: 이진 검색 트리

 

이진검색트리는 세가지 검색법이 있다.

 

1. 전위순회 - root -> left -> right

2. 중위순회 - left -> root -> right

3. 후위순회 - left -> right -> root

 

문제에서는 전위순회로 들어온 값들을 후위순회한 값으로 나타내라고 한다. 처음 생각은 다시 트리를 구성해서 전위순회해야하는건가 싶었는데 불가능하지는 않겠지만 비용이 많이들고 굳이 그럴 필요도 없다.

 

전위순회와 이진탐색트리의 성질을 잘 생각해보자. 전위 순회는 언제나 루트가 먼저온다. 그리고 왼쪽서브트리로 갔다가 오른쪽 서브트리를 방문하게된다. 즉, 루트보다 모두 작은 서브트리를 방문했다가 모두 큰 서브트리를 방문한다는 뜻이다.

 

.

 

주어진 입력을 root left right 로 나타내면 위와 같다.

그리고 left와 righr도 똑같이 나타낼 수 있다. 이 방식을 통해  Divide and Conquer 방식으로 재귀적 풀이가 가능하게 된다.

 

 

그림으로 표현하면 위와 같아진다. index에 따라 left와 right를 구별하고 한개의 원소만 남았을 때 함수를 끝내는 방식이다.

 

이진 탐색 트리와 순회법, 그리고 분할정복, 재귀까지 떠올려야하는 좋은문제였다.

그리고 EOF를 사용자가 입력하기 위해서는 컨트롤 + d 를 하면된다!

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> values;
void recusion(int s, int e) {
	if (s >= e) return;

	int isBound = s + 1;

	for (int i = s + 1; i < e; i++) {
		if (values[s] < values[i]) {
			isBound = i;
			break;
		}
	}

	recusion(s + 1, isBound);
	recusion(isBound, e);
	cout << values[s] << '\n';
}

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

	int tmp;
	while (cin >> tmp) {
		values.push_back(tmp);
	}

	recusion(0, values.size());

	return 0;
}