[백준 5639번 C/C++] 이진 검색 트리

 

[백준 5639번 C/C++] 이진 검색 트리

 

 

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

5639번: 이진 검색 트리

---

 

해결전략

 

깊이 우선 탐색 DFS

트리 후위 순회

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;

void DFS(int start, int end)
{
	if (start >= end) {
		return;
	}
	if (start == end - 1) {
		cout << v[start] << "\n";
		return;
	}

	int idx = start + 1;
	while (idx < end)
	{
		if (v[start] < v[idx]) break;

		idx++;
	}

	DFS(start+1, idx);
	DFS(idx, end);
	cout << v[start] << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	int input;
	while (cin >> input){
		v.push_back(input);
	}
	int n = v.size();

	DFS(0, n);

	return 0;
}

 

 

---