[BOJ] 5639번 이진 검색 트리 (C++)

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

5639번: 이진 검색 트리

 

#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 num;
	int ipidx = 0;
	while(cin >> num){
		tree[ipidx++] = num;
	}
	
	postOrder(0, ipidx);
	return 0;
}

트리의 전위 순회가 입력으로 주어졌을 때, 이를 가지고 후위 순회 결과를 출력하는 문제이다.

전위 순회 결과가 다음과 같다면

50

30

24

5

28

45

98

52

60

루트 노드는 50이고, 루트 노드보다 큰 값이 나오기 전까지는 모두 루트 노드의 왼쪽 자식들일 것이다. (root, left, right)

left, right, root 순으로 재귀를 돌려주면 후위 순회 결과를 출력할 수 있다.