108. Convert Sorted Array to Binary Search Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        
        mid = len(nums) // 2
        
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        
        return root

 

배열이 먼저 정렬되어 있어야 한다.

 

이진 검색을 하는 것과 유사하게 구현한다. 숫자 리스트 중 중앙값보다 작은 값이 왼쪽, 중앙값보다 큰 값이 오른쪽으로 오게 하고, nums의 범위를 변경함으로써 재귀 탐색을 한다.

 

// 내림 연산자를 사용하여 중앙값을 탐색할 수 있게 한다.