108.-convert-sorted-array-to-binary-search-tree.md

108. Convert Sorted Array to Binary Search Tree

• Easy
• 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.
• https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Solution 1

Runtime: 52 msMemory Usage: 15.7 MB

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums)==0:
            return 
        mid=len(nums)//2
        root = TreeNode(nums[mid])
        
        root.left=self.sortedArrayToBST(nums[0:mid])
        root.right=self.sortedArrayToBST(nums[mid+1:])
        return root

{% hint style="info" %} This solution uses recursive method to set the tree. Since the list is given in ascending order, the value at the current node is the mid value of the current list of numbers. {% endhint %}

Solution 2

Runtime: 52 msMemory Usage: 15.7 MB

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def sort(left,right):
            if left>right:
                return None
            mid=(left+right)//2
            node=TreeNode(nums[mid])
            node.left=sort(left,mid-1)
            node.right=sort(mid+1,right)
            return node
        return sort(left=0,right=len(nums)-1)

{% hint style="info" %} This method is the same in using recursive method. However, slicing a list like solution 1 would be costly. So this solution uses the lower and upper bound for the recurse. {% endhint %}