백준 9934번 완전 이진 트리 C++

문제

www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

코드

#include<bits/stdc++.h>

using namespace std;

vector<int> ret[11];
int n, a[1030];

void go(int start, int end, int depth)
{
	if (start > end)
		return;

	// 마지막 depth일 경우
	if (start == end)
	{
		ret[depth].push_back(a[start]);
		return;
	}

	int mid = (start + end) / 2;
	ret[depth].push_back(a[mid]);
	go(start, mid - 1, depth + 1);
	go(mid + 1, end, depth + 1);

	return;
}

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

	cin >> n;
	int end = (int)pow(2, n) - 1;
	for (int i = 0; i < end; i++)
	{
		cin >> a[i];
	}

	go(0, end, 1);
	
	for (int i = 1; i <= n; i++)
	{
		for (int j : ret[i])
		{
			cout << j << " ";
		}
		cout << "\n";
	}

	return 0;
}

삼각형 단위로 go 함수를 실행한다.

go 함수를 실행하는 순서는 3-6-1-4-2-5-7 이고 depth를 이용해서 계층별 자식값을 가져오게 된다.

 

위 정답 코드는 아래와 같이 출력하는데

 

만약 go 코드에서 go 순서를 다음과 같이 바꾸면 다음과 같이 출력된다.

	int mid = (start + end) / 2;
	ret[depth].push_back(a[mid]);
	go(mid + 1, end, depth + 1);
	go(start, mid - 1, depth + 1);