백준 5639 - 이진 검색 트리

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 이진 탐색 트리의 전위 순회 결과가 주어지면 후위 순회를 진행한 결과를 출력하면 된다.

 

해당 문제는 이진 탐색 트리의 특징을 활용하면 된다.

이진 탐색 트리의 특징은 왼쪽 자식 노드는 자신보다 작으며 오른쪽 자식 노드는 자신보다 크다는 것이다.

 

전위 순회와 후위 순회의 차이는 루트를 가장 먼저 출력하는 것과 가장 늦게 출력하는 것의 차이이다.

즉, 루트를 시작으로 왼쪽 자식과 오른쪽 자식을 나눈 후 루트를 나중에 출력하면 후위 순회가 된다.

 

왼쪽 자식과 오른쪽 자식을 나누는 기준은 루트보다 큰지 작은지로 나누면 된다.

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

 

두 구간을 나눴다면 왼쪽 자식에 재귀, 오른쪽 자식에 재귀를 진행하고 루트를 출력하면 된다.

make(start + 1, idx);
make(idx, end);

cout << nums[start] << '\n';

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<int> nums;

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

	if (start == end - 1) 
	{
		cout << nums[start] << '\n';
		return;
	}

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

	make(start + 1, idx);
	make(idx, end);

	cout << nums[start] << '\n';
}

int main() 
{
    INPUT_OPTIMIZE;

	int num;
	while (cin >> num)
	{
		nums.push_back(num);
	}

	make(0, nums.size());

	return 0;
}

---