[BOJ] 5639 이진 검색 트리

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

5639번: 이진 검색 트리

알고리즘: 트리 순회, 재귀

---

트리의 전위순회를 후위순회로 바꾸면 AC

 

좌노드 방문 -> 우노드 방문 -> 방문할 곳이 없으면 자기 자신 출력

 

구간을 [l, r]로 잡아주고,

왼쪽 자식을 탐색할 때: [l, 부모 노드 값)

오른쪽 자식을 탐색할 때: (부모 노드 값, r] 

로 구간이 바뀐다는 이진 트리의 특성을 이용하여 재귀함수 구현

 

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	int inOrder[10002], idx, N;
	void sol(int l, int r){
	int cur = inOrder[idx];
	idx++;
	if (inOrder[idx] < cur && inOrder[idx] > l){
	sol(l, cur);
	}
	if (inOrder[idx] > cur && inOrder[idx] < r){
	sol(cur, r);
	}
	printf("%d\n", cur);
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	while (cin >> inOrder[N++]);
	sol(0, 1e7);
	}

view raw BOJ_5639.cpp hosted with ❤ by GitHub