[백준][이진 트리][이분 탐색] 9934 완전 이진 트리

목차

1. 문제
2. 문제 구현 방향
3. 코드 구현

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

문제

 

문제 구현 방향

중위 순회가 무엇인지 알면 쉽게 풀 수 있는 문제이다.

start 와 end를 통해서 인자를 전달하고 mid를 통해서 탐색해주면 되는 이분 탐색을 이용한다.

 

 

혹시나 모른다면 참고

https://be-senior-developer.tistory.com/17

[이진트리] 기본 c++구현 및 이진 트리 순회 설명(전위,중위,후위)

 

코드 구현

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <math.h>
using namespace std;

int maxsize;
int arr[1050] = { 0 };
vector<int> Level[20];
void binary(int start, int end, int level) {
	int mid = (start + end) / 2;
	Level[level].push_back(arr[mid]);
	if (start >= end)
		return;
	level++;
	binary(start, mid - 1, level);
	binary(mid+1, end, level);

}

int main() {
	int n;
	cin >> n;
	maxsize = pow(2, n) - 1;
	for (int i = 0; i < maxsize; i++) {
		cin >> arr[i];
	}
	binary(0, maxsize - 1, 0);
	for (int i = 0; i < 15; i++) {
		if (!Level[i].empty()) {
			for (int p : Level[i])
				cout << p << " ";
			cout << "\n";
		}
	}

}
/*

*/