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

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

9934번: 완전 이진 트리

* 탐색결과를 트리로원복

 

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;
}