My Python solution, 116ms


  • 0
    S

    Since the list is already sorted, the middle element will be the root of the new BST. Then after setting the root, recursively build the left and right subtrees of the BST by using the the half of the array less than mid and the half greater than mid respectively.

    class Solution(object):
            def sortedArrayToBST(self, nums):
                """
                :type nums: List[int]
                :rtype: TreeNode
                """
                if not nums:
                    return None
                
                if len(nums) <= 1:
                    return TreeNode(nums[0])
                
                mid = len(nums)//2
                
                root = TreeNode(nums[mid])
                root.left = self.sortedArrayToBST(nums[:mid])
                root.right = self.sortedArrayToBST(nums[mid+1:])
                
                return root

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.