[백준]5639_이진 검색 트리

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

Solved

✔ 그래프 이론 / 그래프 탐색 / 트리 / 재귀
✔ 그래프 문제는 볼 때마다 새로워!
✔ 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

✔ 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하자
✔ 이 문제는 입력의 끝을 알아서 체크해야 한다. 그래서while(!cin.eof()) 를 사용했다.

✔ 전위순회: root→leftChild→rightChild 순으로 탐색한다. 즉, 첫번째 노드보다 큰 값이 시작 하는 노드가 rightChild 이다. upper_bound를 사용했다. 그 뒤로 출력은 후위순회와 같이 하면 된다.

using namespace std;
#include <iostream>
#include <algorithm>
#define MAX 10000

int preorder[MAX];

void postorder(int start, int end) {
	if (start >= end) {
		return;
	}
	auto it = upper_bound(preorder + start, preorder + end, preorder[start]);
	int dist = it-preorder; //==distance(preorder,it) distance: iterator 사이의 크기를 반환한다.
	postorder(start + 1, dist);
	postorder(dist, end);
	cout << preorder[start] << '\n';
}
int main() {
	int n;
	int i = 0;
	while (!cin.eof()) {
		cin >> preorder[i++];
	}
	postorder(0, i-1);
}