[백준] 9934 OBILAZAK

백준 9934 OBILAZAK

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

• 트리의 중위 순회 결과값으로 완전 이진 트리(A perfect binary tree) 만들기

• 완전 이진 트리이기 때문에 배열 하나로 노드들을 표시할 수 있다
  루트 노드를 1로 잡으면, 모든 노드들에 대해서 왼쪽 자식은 2$*$n , 오른쪽 자식은 2$*$n + 1 이 된다

#include <iostream>
#include <math.h>
using namespace std;

int k;
int perfectBinaryTree[1025] = { 0 };
int sequence[1025] = { 0 };

void getPerfectBinaryTree(int start, int end, int nodeNum) {
	if (nodeNum > pow(2, k) - 1) return;

	int mid = (start + end) / 2;
	perfectBinaryTree[nodeNum] = sequence[mid];

	//left Child
	getPerfectBinaryTree(start, mid - 1, nodeNum * 2);
	//right Child
	getPerfectBinaryTree(mid + 1, end, nodeNum * 2 + 1);
	return;
}

void printPerfectBinaryTree() {
	int index = 1;

	for (int i = 0; i < k; ++i) {
		for (int j = 0; j < pow(2, i); ++j) {
			cout << perfectBinaryTree[index] << " ";
			++index;
		}
		cout << "\n";
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> k;
	int numOfNodes = pow(2, k) - 1;

	int input;
	for (int i = 1; i <= numOfNodes; ++i)
		cin >> sequence[i];
	
	getPerfectBinaryTree(1, numOfNodes, 1);
	printPerfectBinaryTree();
	return 0;
}

다른 풀이 (22.12.22)

• 중위 순회 결과의 중앙이 루트 임을 이용한 풀이

• 1 6 4 3 5 2 7
  -> (1 6 4)(3)(5 2 7)
  -> (1 (6) 4)(3)(5 (2) 7)
  -> ((1) (6) (4))(3)((5) (2) (7))

• tree[0] = {3}
  tree[1] = {6, 2}
  tree[2] = {1, 4, 5, 7}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int k;
vector<int> nodes;

//tree[i]: 위에서부터 i번째 깊이에 있는 노드들의 번호
vector<vector<int>>tree;

void buildTree(int depth, int start, int end) {
	int root = (start + end) / 2;
	tree[depth].push_back(nodes[root]);

	if (start == end) return;

	buildTree(depth+1, start, root - 1);
	buildTree(depth+1, root + 1, end);
	return;
}

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

	cin >> k;	

	for (int i = 0; i < k; ++i) {
		tree.push_back(vector<int>());
	}

	while(true){
		int input;
		cin >> input;
		if (cin.eof()) break;

		nodes.push_back(input);
	}
	
	buildTree(0, 0, nodes.size()-1);

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