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

 

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

5639번: 이진 검색 트리

 

문제 설명 : 

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

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

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

입력 : 

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력 : 

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

예제 입력 : 

50
30
24
5
28
45
98
52
60

예제 출력 : 

5
28
24
45
30
60
52
98
50

 

 

접근법 : 

1) 어떻게 풀 것인가?

input : 전위순회     (root -> left -> right )

              ↓ 

output : 후위순회   (left -> right -> root )

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 이진 검색 트리 5639 C++ 
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (10000+3)

using namespace std;

int tree[MAX];
int pt;

void postOrder(int start, int end);

int main() {

	//freopen("input.txt", "r", stdin);

	int input;
	pt = 0;
	while (scanf("%d", &input) != EOF) {
		tree[pt++] = input;
	}

	postOrder(0, pt);

	return 0;
}


void postOrder(int start, int end) {
	// ** 탈출조건
	if (start >= end) return;

	int i;
	for (i = start + 1; i < end; i++) {
		if (tree[start] < tree[i]) {
			break;
		}
	}
	
	postOrder(start + 1, i);
	postOrder(i, end);
	printf("%d\n", tree[start]);
	
}
#endif