[파이썬 알고리즘 인터뷰] 22. 배열의 이진 탐색 트리 변환

1. 문제

leetcode 108. Convert Sorted Array to Binary Search Tree
주어진 정렬된 배열을 모든 서브트리의 높이 차이가 2 이상 나지 않는 이진 탐색 트리로 바꾸어라.

2. 해결 방법

재귀 방식의 dfs로 문제를 풀었다. 함수는 인자로 자신과 자식노드들의 값이 될 배열의 값을 전달받고, 노드를 만들어 리턴한다. 먼저 배열의 가운데 위치한 값을 루트노드의 값으로 지정한다. 가운데 값은 몫을 계산하는 //  연산자를 이용해 계산한다. 그리고 그 값 기준으로 왼쪽에 있는 값들의 리스트는 왼쪽노드를 생성할 재귀함수의 인자로, 오른쪽에 있는 값들의 리스트는 오른쪽 노드를 생성할 재귀함수의 인자로 전달한다. 각 함수의 실행이 끝나면 node.left, node.right에 왼쪽/오른쪽 자식 노드가 연결되게 된다.

3. 전체 코드

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None

        mid = len(nums) // 2

        # 분할 정복으로 이진 검색 결과 트리 구성
        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid + 1:])

        return node