[LeetCode 108] Convert Sorted Array to Binary Search Tree

정렬된 배열의 이진 탐색 트리 변환

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

 

Think

BST의 원리를 이해한다면 쉽게 풀 수 있는 문제였다!

(기억이 잘 안나서 BST 개념이랑 특징 따로 읽어봤음)

주어지는 배열도 정렬된 배열이라 간단했다~

 

 

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        
        if not nums :
            return None
        
        mid = len(nums)//2 #몫을 정수(내림)로 리턴하는 나눗셈 몫 연산자
        
        #분할 정복 (재귀)
        #아래 세 코드는 현재 주어진(정렬된) 배열에 대래 계속 중앙값을 기준으로 나누는 작업을 하므로
        #이것만 재귀로 반복해주면 정렬된 배열을 계속 반으로 쪼개서 만든 이진탐색트리BST가 됨!!
        node = TreeNode(nums[mid]) #정렬된 배열의 중앙값을 루트노드로 시작. 
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid+1:])
        
        return node

 

 

 

Get