Convert Sorted Array to Binary Search Tree

•

문제 링크 : LeetCodeConvert Sorted Array to Binary Search Tree - LeetCode

•

문제 설명 : 제공된 배열을 사용하여, 간단한 이진 탐색 트리를 만들기

•

풀이 방법 : 하위 트리는 반복적으로 탐색을 해야하며, 이때는 재귀를 사용한다. 더 이상의 하위 트리를 만들 수 없을 때까지 진행하고, 빠져나온다.

◦

이 문제를 통해 재귀를 사용한 문제의 break를 잘 사용하는 방법을 확인

•

성공 코드

# 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
# O(N/2) + O(N/2) -> O(N)만큼 소요
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        
        # 더 이상 추가로 나눌 하위 트리가 없는 경우
        # not 연산자 -> __bool__ 메서드를 호출 / 없다면 __len__을 호출함 -> O(1)
        if not nums:
            return None
				
				# len() 함수 호출 -> __len__ 호출 -> O(1)
        # 중간 부분을 구함
        mid = len(nums) // 2

        # 좌/우 하위 트리를 재귀로 구함
        root = TreeNode(nums[mid]) # 직접 접근 O(1)
        
        # nums의 절반만큼을 처리 O(N/2)
        # 재귀이지만, 결국에는 인자로 넣은 모든 노드의 갯수(N)만큼 처리하기 때문에, O(log2N)은 아니다.
        root.left = self.sortedArrayToBST(nums[:mid])
        
        # # nums의 절반만큼을 처리 O(N/2)
        root.right = self.sortedArrayToBST(nums[mid + 1 :])

        # 현 TreeNode 노드를 반환
        return root
Python
복사