Q.

각기 다른 integer를 가진 오름차순으로 정렬된 배열이 있다고 했을 때, 최소 높이의 BST를 가지는 알고리즘을 작성하라.

출처 : Cracking The Coding Interview Q 4.2

My Solution

class Tree:
    class Node:
        def __init__(self, data):
            self.data = data
            self.left = None
            self.right = None


    def __init__(self):
        self.root = None


    def minimal_height_BST(self, arr):
        self.root = self.int_to_node(arr)


    def int_to_node(self, arr):
        if len(arr) == 0:
            return None

        if len(arr) == 1:
            return self.Node(arr[0])

        mid = int(len(arr) / 2)
        n = self.Node(arr[mid])
        n.left = self.int_to_node(arr[:mid])
        n.right = self.int_to_node(arr[mid + 1:])
        return n

다른 Solution

int_to_node(self, arr, start, end) 로 구현하기

왜?
: 배열을 슬라이싱해서 인수(arguments)로 넘겨주면 공간 복잡도(space complexcity)가 커진다.