[LEET CODE] 108. Convert Sorted Array to Binary Search Tree

# Problem

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.   Constraints: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums is sorted in a strictly increasing order.

 

# My Answer

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def sortarray(lst):
            node = TreeNode(lst[len(lst)//2])
            if len(lst)<=3 and len(lst)>=1:
                if len(lst)>=2: # 길이가 2이상이면 왼쪽, 오른쪽 모두 존재
                    node.left = TreeNode(lst[0])
                if len(lst)==3: # 길이가 3인 경우 오른쪽 노드 
                    node.right = TreeNode(lst[2])
                return node 
            node.left = sortarray(lst[:len(lst)//2])
            node.right = sortarray(lst[len(lst)//2+1:])
            return node
            
        return sortarray(nums)

 

# Solution 1

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

따로 함수 만들 필요없이 재귀호출

입력된 리스트의 가운데 값이 루트 노드가 되고,

가운데 노드 기준으로 왼쪽, 오른쪽 나눠서 또 각각의 가운데 값이 제일 상위 노드가 되는 과정 반복