[코딩인터뷰 완전정복] 4.2 최소트리

Q : 오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라.

template <class T>
class TreeNode{
public:
	T data;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;

	TreeNode(T data) {
		this->data = data;
	}
};

template <class T>
class ListNode {
	T data;
	ListNode* previous;
	ListNode* next;

	ListNode(T data) {
		this->data = data;
	}
};

#include <iostream>
#include "Node.h"

TreeNode<int>* MinimumTree(int* sortedArray, int start, int end) {

	if (start > end) return NULL;

	int center = (start + end + 1) / 2;

	printf("%d Start : %d, End : %d\n", sortedArray[center], start, end);
	TreeNode<int>* node = new TreeNode<int>(sortedArray[center]);
	node->left = MinimumTree(sortedArray, start, center - 1);
	node->right = MinimumTree(sortedArray, center + 1, end);

	return node;
}

TreeNode<int>* MinimumTree(int* sortedArray, int length) {
	
	return MinimumTree(sortedArray, 0, length - 1);
}

void printTree(TreeNode<int>* tree) {
	printf("%d : ", tree->data);
	if(tree->left!=NULL)
		printf("L %d ", tree->left->data);
	if (tree->right != NULL)
		printf("R %d", tree->right->data);
	printf("\n");
	if (tree->left != NULL)
		printTree(tree->left);
	if (tree->right != NULL)
		printTree(tree->right);
}

int main() {

	int array[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	for (int i = 0; i < 10; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");
	printTree(MinimumTree(array, 10));
	printf("\n");
}

중앙에 있는 원소를 가운데에 두고 왼쪽에 있는 원소는 왼쪽 트리에, 오른쪽에 있는 원소는 오른쪽 트리에 삽입한다.

재귀 호출을 통해 반복한다.