취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5639번 문제인 이진 검색 트리이다.
문제는 아래 링크를 확인하자.

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

각 노드를 루트로 하는 BST(binary search tree; 이진 검색 트리)는 그 수보다 작은 수들만으로 구성된 왼쪽 subtree와 큰 수들만으로 구성된 오른쪽 subtree로 이루어져있다는 점에 주목하여 재귀적으로 문제를 해결해보자.

주어진 BST가 조건에 주어진 키값 최댓값인 100만보다 큰 수를 root로 갖는 BST의 왼쪽 subtree라고 가정해도 모순이 생기지 않으므로, 아래와 같은 구현이 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int idx = 0;
int arr[10001];

void func(int root) {
	int val = arr[idx++];
	if (arr[idx] < val) func(val);
	if (arr[idx] < root) func(root);
	cout << val << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int x, idx = 0;;
	while (cin >> x) {
		arr[idx++] = x;
	}

	arr[idx] = 1000000007;
	idx = 0;
	func(1000000000);
}