Python optimal solution


  • 2

    For a sorted array, the left half will be in the left subtree, middle value as the root, right half in the right subtree. This holds through for every node:

    [1, 2, 3, 4, 5, 6, 7] -> left: [1, 2, 3], root: 4, right: [5, 6, 7]
    [1, 2, 3] -> left: [1], root: 2, right: [3]
    [5, 6, 7] -> left: [5], root: 6, right: [7]

    Many of the approaches here suggest slicing an array recursively and passing them. However, slicing the array is expensive. It is better to pass the left and right bounds into recursive calls instead.

    - Yangshun

    class Solution(object):
        def sortedArrayToBST(self, nums):
            # Time: O(n)
            # Space: O(n) in the case of skewed binary tree.
            def convert(left, right):
                if left > right:
                    return None
                mid = (left + right) // 2
                node = TreeNode(nums[mid])
                node.left = convert(left, mid - 1)
                node.right = convert(mid + 1, right)
                return node
            return convert(0, len(nums) - 1)
    

  • 1

    @yangshun I agree with you that slice is expensive. Here is my solution similar to yours.

    class Solution:
        def sortedArrayToBST(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            return self.build(nums, 0, len(nums)-1)
        
        def build(self, nums, low, high):
            if low == high:
                return TreeNode(nums[low])
            elif low < high:
                mid = (low+high)//2
                node = TreeNode(nums[mid])
                node.left = self.build(nums, low, mid-1)
                node.right = self.build(nums, mid+1, high)
                return node
    

Log in to reply
 

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