[Baekjoon] 5639번: 이진 검색 트리

🥅 문제

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

 

🔍 설계

입력으로 주어진 50 30 24 5 28 45 98 52 60 에서 루트, L, R을 구분하면, 50 30 24 5 28 45 98 52 60 이다.

L, R 서브트리 각각의 서브트리를 구해도 루트는 첫 번째, L은 두 번부터 루트보다 작은 수까지, R은 루트보다 큰 수부터 끝까지라는 것을 알 수 있다.

 

서브 트리에 해당하는 인덱스의 범위를 재귀로 만들어서 LRV를 진행하면 된다.

 

주의해야할 점은 개수가 정해져 있지 않기 때문에, while을 이용하여 벡터에 입력값을 지정했는데, 이럴 경우 최종 인덱스는 마지막 인덱스보다 하나 더 많은 총 개수이다. 따라서 범위를 지정할 때, end는 사용되지 않는다는 것에 유의해야 한다.

 

👊 풀이

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

vector<int> tree(10000);

void postOrder(int start, int end) {
	if (start >= end) {
		return;
	}
	if (start == end - 1) {
		cout << tree[start] << "\n";
		return;
	}
	int root = tree[start];
	int branch_idx = start + 1;
	while (branch_idx < end) {
		if (root < tree[branch_idx]) {
			break;
		}
		branch_idx += 1;
	}
	postOrder(start + 1, branch_idx);
	postOrder(branch_idx, end);
	cout << tree[start] << "\n";
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);	
	
	int num;
	int cur_idx = 0;

	while (cin >> num) {
		tree[cur_idx++] = num;
	}

	postOrder(0, cur_idx);

	return 0;
}