[알고리즘] 정렬된 배열의 이진 탐색 트리 변환

이진 탐색 트리(BST)는 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다.

책 풀이

class Solution:
    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

정확히 리스트의 중앙이 부모노드이다. 이를 재귀적으로 진행하면 된다.