백준 5639 이진 검색 트리 (c++) : 피너클

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

5639번: 이진 검색 트리

트리문제다.

전위 순회한 결과를 후외 순회한 결과로 바꿔야한다.

전위 순회는 (루트 - 왼쪽 - 오른쪽) 순서고 후위 순회는 (왼쪽 - 오른쪽 - 루트) 순서다.

전위 순회는 무조건 맨 처음이 루트다.

그리고 루트 다음은 왼쪽 루트고 

루트 이후에 나오는 숫자중 루트보다 큰 숫자중 첫번째가 오른쪽 루트다.

int num;
while (cin >> num) {
	arr[len++] = num;
}

값은 이렇게 입력받는다.

void solve(int start, int end) {
	if (start >= len) return;

solve함수다. solve함수는 범위안의 트리를 후위 순회 시킨다.

solve함수는 트리의 가장 왼쪽과 트리의 가장 오른쪽을 전달받는다.

만약 트리의 가장 왼쪽이 트리의 길이보다 높다면 바로 종료시킨다.

	int root = start;
	int left = (arr[start] > arr[start + 1] ? start + 1 : -1);

루트는 무조건 첫번째 숫자다.

그리고 왼쪽 무조건 루트의 다음이다. 그런데 여기서 루트 다음에 왼쪽이 없고 바로 오른쪽이 나오는 경우가 있다.

그러니 루트의 다음이 루트보다 작다면 left를 start + 1로 저장하고 크다면 -1로 저장한다.

	int right = -1;
	for (int i = start + 1; i < end; i++) {
		if (arr[root] < arr[i]) {
			right = i;
			break;
		}
	}

오른쪽은 루트보다 큰 숫자중 첫번째 숫자다. 루트 이후의 배열을 돌아 찾아낸다.

만약 루트보다 큰 숫자가 이후에 없는경우 right는 -1로 진행된다.

	if (left != -1) {
		if (right == -1) solve(left, end);
		else solve(left, right);
	}

만약 left가 -1이 아니라면 왼쪽을 순회한다.

여기서 right가 -1이라면 left부터 end까지 순회하고 

right가 -1이 아니라면 left부터 right까지 순회한다.

	if (right != -1) solve(right, end);

만약 right가 -1이 아니면 right부터 end까지 순회한다.

	cout << arr[root] << '\n';
}

마지막으로 arr[root]를 출력한다.

#include <iostream>

using namespace std;

int len = 0;
int arr[10001];

void solve(int start, int end) {
	if (start >= len) return;

	int root = start;
	int left = (arr[start] > arr[start + 1] ? start + 1 : -1);
	int right = -1;
	for (int i = start + 1; i < end; i++) {
		if (arr[root] < arr[i]) {
			right = i;
			break;
		}
	}

	if (left != -1) {
		if (right == -1) solve(left, end);
		else solve(left, right);
	}
	if (right != -1) solve(right, end);

	cout << arr[root] << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int num;
	while (cin >> num) {
		arr[len++] = num;
	}
	solve(0, len);
}

전체코드다.