Leetcode 108. Convert Sorted Array to Binary Search Tree

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

Convert Sorted Array to Binary Search Tree - LeetCode

문제를 풀기 위한 생각의 흐름

 

Inorder traversal을 하면 결국 sorted array가 되잖아?

 

만약 height balanced BST가 아니라면 그냥 왼쪽에서부터 쭉 만들어주면 되는데. 그럴리가 없음.

 

좀 더 생각하다가 나온 것은, 항상 가운데 요소를 root로 만들어주면 되는거 아닌가? 하는 생각이 들음.

-> 이거는. 요소의 갯수가 있으면, 내 val에 상관 없이 항상 갯수에 따른 tree가 정해져있다는 생각에서 나옴.

예를 들어 6개의 요소가 있다고 하면, 항상  1, 2, 3의 요소가 있는 트리를 만들어줄 수 있다고 생각하게 됨.

 

그걸 만드는거로 가장 쉬워보이는게 가운데 요소를 root로 재귀적으로 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]) -> TreeNode:

        def sortToBST(nums):

            if len(nums) == 0:

                return None

            mid = nums[len(nums) // 2]

            root = TreeNode(mid)

            root.left = sortToBST(nums[:len(nums) // 2])

            root.right = sortToBST(nums[len(nums) // 2 + 1:])

            return root

        return sortToBST(nums)

 

시간 복잡도가 O(n) 이라고 생각했는데, 파이썬 slicing 시간 복잡도가 O(n) 이어서 O(nlogn)이 된다. 이를 막기 위해서 nums list는 냅두고 idx를 주는 방식으로 하면 시간 복잡도를 줄일 수 있을 것이다.