[백준 9934번] 완전 이진 트리 (C++)

문제링크 : https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int k, num;
int arr[1024];
vector<int>result[10];

void tree(int left, int right, int height)
{
	if (left == right)
	{
		result[height].push_back(arr[left]);  //left == right이면 남은 노드가 1개이므로 종료
		return;
	}

	int mid = (left + right) / 2;

	result[height].push_back(arr[mid]);  //현재 높이에 중앙값 푸쉬

	tree(left, mid - 1, height + 1);   //좌측 탐색
	tree(mid + 1, right, height + 1);  //우측 탐색
}


int main()
{
	fastio;
	cin >> k;

	num = pow(2, k) - 1;  //트리 최대 길이
	for (int i = 0; i < num; i++)
	{
		cin >> arr[i];
	}

	tree(0, num - 1, 0);  //길이가 7이면 배열은 0 ~ 6, 높이 0부터 시작

	for (int i = 0; i < k; i++)  //높이 (해당 층)
	{
		for (int j = 0; j < result[i].size(); j++)  //해당 층의 노드 출력
		{
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}

 

배열의 중앙값은 부모 노드이다.

그러므로 처음에 중앙값을 계산하여 푸쉬하여 첫 층을 만들고 그 중앙을 기준으로 좌측과 우측을 탐색한다.

이때 앞서서 중앙값을 계산할때 첫 층을 만들었기에, 층의 카운트를 같이 넘겨준다.

 

마찬가지로 좌측에서의 중앙값이 부모노드가 되고, 우측에서의 중앙값이 부모노드가 된다.

만약 left와 right가 같다면, 이것은 남은 노드가 1개여서 더이상 탐색할 것이 없다는 것을 의미한다.

따라서 위의 경우에는 해당 층에 해당 값을 넣고 재귀를 종료하게된다.

 

재귀함수인 tree에 (0, num - 1, 0)을 넣었는데 총 길이는 num이나, 0부터 시작하기에 num - 1을 하였다.

만약 num - 1이 아닌 num을 넣을 것이라면 (1, num, 0)으로 하여야한다.

 

이후 이중반복문을 통해서 해당 층(i)에서 해당 층의 길이(result[i].size())만큼 해당 값인 j를 출력시켜준다.