[백준 BOJ][C++]9934번 완전 이진 트리 풀이: 트리

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

9934번: 완전 이진 트리

 

 입력 k는 완전 이진 트리의 깊이를 나타내고, 배열은 트리 내 노드를 중위 순회(inorder)한 순서입니다. 

 

 먼저 트리 내 노드의 개수를 알아야겠죠? 완전 이진 트리의 깊이 k가 알려졌을 때 총 노드의 수는 다음과 같습니다.

 중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 탐색하는 방법입니다. 

 

 이제 문제를 해결하기 위한 사전 지식은 갖춰졌으니 문제를 풀어보겠습니다.

 

 먼저 depth 1에는 루트 노드 하나만 있겠죠? 루트 노드는 완전 이진 트리를 중위 순회한 배열에서도 가운데에 위치해있습니다. 

 

index	0	1	2	3	4	5	6
원소	1	6	4	3	5	2	7

 

 루트노드를 찾았다면 해당 원소를 트리 배열에 저장합니다. 

 

 

 이제 왼쪽 서브 트리로 이동하겠습니다. 

 

 왼쪽 서브 트리 index 0부터 2까지의 중간 원소인 6이 왼쪽 서브 트리의 부모 노드가 됩니다. 

index	0	1	2	3	4	5	6
원소	1	6	4	3	5	2	7

 

 오른쪽 서브 트리도 마찬가지 입니다. 

index	0	1	2	3	4	5	6
원소	1	6	4	3	5	2	7

 

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

int k;
int num;
int arr[1050];
vector<int> tree[10];

void solution(int s, int e, int d) {
	if (d >= k)
		return;

	if (s == e) { //리프 노드 
		tree[d].push_back(arr[s]);
		return;
	}

	int m = (s + e) / 2;

	if (m < 0 || m >= num)
		return;

	tree[d].push_back(arr[m]); //중간 값 트리 내 depth d에 push

	solution(s, m - 1, d + 1); //왼쪽 서브 트리
	solution(m + 1, e, d + 1); //오른쪽 서브 트리 

}

int main(void) {

	cin >> k;

	num = pow(2, k) - 1;

	for (int i = 0; i < num; i++) {
		cin >> arr[i];
	}

	solution(0, num - 1, 0);

	for (int i = 0; i < k; i++) {
		for (int j = 0; j < tree[i].size(); j++) {
			cout << tree[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}