관리 메뉴

Mini

백준 9934 완전이진트리 // 탐색결과를 트리로원복 본문

Algorithm/boj

백준 9934 완전이진트리 // 탐색결과를 트리로원복

Mini_96 2023. 6. 28. 17:17

9934번: 완전 이진 트리 (acmicpc.net)

 

9934번: 완전 이진 트리

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래

www.acmicpc.net

* 탐색결과를 트리로원복

 

1 6 4 3 5 2 7

mid를 푸쉬, 재귀적으로 mid를 푸쉬하면된다.

3

6, 2

...

종료조건국룰 : start>end   ----> return;

종료조건 : start==end -> push(mid==start==end), return

 

#include<bits/stdc++.h>
using namespace std;
int _end,n;
vector<int> ret[14];
int a[1030];	//최대노드수 : 2^10-1

void go(int s, int e, int level) {
	if (s > e) return; //국룰예외처리
	if (s == e) {
		ret[level].push_back(a[s]);
		return;
	}

	int mid = (s + e) / 2;
	ret[level].push_back(a[mid]);
	go(s, mid - 1, level + 1);
	go(mid + 1, e, level + 1);
}
int main() {
	cin >> n;
	_end = (int)pow(2, n) - 1;
	for (int i = 0; i < _end; i++) {
		cin >> a[i];	//노드저장
	}
	go(0,_end, 0);
	for (int i = 0; i < n; ++i) {
		for (auto j : ret[i]) {
			cout << j << " ";		
		}
		cout << "\n";
	}
	
	return 0;
}