[LeetCode] #108: Convert Sorted Array to Binary Search Tree

Kyu Hwan Choi·2022년 5월 4일
0

LeetCode

목록 보기
6/11
post-thumbnail

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.


Process:

Objective: Convert the sorted array into BST

Constraints:
1. 1 <= nums.length <= 10^4
2. -10^4 <= nums[i] <= 10^4
3. nums is sorted in a strictly increasing order.

Edge Cases:

  • When nums is an empty list. (According to the constraints, nums has to have at least one element)

Additional Details:

  • Height-balanced Binary Tree: A binary tree in which the depth of the two subtrees of every node never differs by more than one.

Solution:

Approach #1: Cut nums in half to create TreeNode and recurse through left and right half to assign children

  • Time Complexity: O(nlogn) due to array slicing
  • Space Complexity: O(nlogn) due to array slicing

How it works:
1. Slice the nums array into half.
2. Create TreeNode with the middle value of nums array.
3. Assign left and right child of the node using recursion with the left and right end of nums array.

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        index = len(nums) // 2
        left_index = index // 2
        right_index = index + ((len(nums) - index) // 2)
        
        node = TreeNode(val = nums[index])
        
        if nums[index] == nums[left_index]:
            node.left = None
        else:
            node.left = self.sortedArrayToBST(nums[0:index])
        
        if nums[index] == nums[right_index]:
            node.right = None
        else:
            node.right = self.sortedArrayToBST(nums[index+1:])
        
        return node 

Limitations:
1. It takes too much time and space due to array slicing.


Approach #2: Recursion w/o Array Slicing

  • Time Complexity: O(logn)
  • Space Complexity: O(logn)

How it works:
1. The recursive function is given with left and right boundary index values of nums array.
2. Set the middle index as the index value and recurse through the array.
3. Once the index value equals the left or right boundary value, they are given with None for left or right child node.

def sliceArray(self, nums, left, right):
        index = left + (right - left + 1) // 2
        node = TreeNode(val = nums[index])
        
        if index == left:
            node.left = None
        else:
            node.left = self.sliceArray(nums, left, index-1)
        
        if index == right:
            node.right = None
        else:
            node.right = self.sliceArray(nums, index+1, right)
        
        return node
        
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.sliceArray(nums, 0, len(nums)-1) 

LeetCode Question #108

0개의 댓글