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

이 문제는 이진 검색 트리를 이용한 문제이다.

 

이진 검색 트리의 전위 순회의 경우, 루-왼-오 순으로 노드를 탐색하고, 후위 순회의 경우 왼-오-루 순으로 탐색한다.

따라서 주어진 범위 내에서의 벡터에서 가장 첫번째 노드는 항상 루트이고, 그 안에서 루트보다 작은 첫번째 값이 왼쪽 서브트리의 루트, 루트보다 큰 첫번째 값이 오른쪽 서브트리의 루트가 된다. 이를 이용해서 풀면 된다.

 

주의할 점은 이진 검색 트리가 최악의 경우 1자로 쭉 이어질 수 있는데, 이를 까먹고 전역 배열을 만들어 원래 트리를 형성하려고 하면 안된다. OutOfBounds 런타임 에러를 만나게 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 10000
#define INF 100000000

vector<int> preorder;

void input() 
{
	while (true)
	{
		int temp;
		
		cin >> temp;
		if (cin.eof())
		{
			break;
		}
		preorder.push_back(temp);
	}
}

int findLeftIndex(const int start, const int end, const int root)
{
	for (int i = start + 1; i < end; i++)
	{
		if (preorder[i] < root)
		{
			return i;
		}
	}

	return end;
}

int findRightIndex(const int start, const int end, const int root)
{
	for (int i = start + 1; i < end; i++)
	{
		if (preorder[i] > root)
		{
			return i;
		}
	}

	return end;
}

void toOridinal(const int index, const int start, const int end)
{	
	const int root = preorder[start];
	const int leftIndex = findLeftIndex(start, end, root);
	const int rightIndex = findRightIndex(start, end, root);

	if (leftIndex < end)
	{
		toOridinal(index * 2, leftIndex, rightIndex);
	}
	
	if (rightIndex < end)
	{
		toOridinal(index * 2 + 1, rightIndex, end);
	}

	cout << root << '\n';
}

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

	input();

	toOridinal(1, 0, preorder.size());

	return 0;
}