Recursive Python solution, no extra space used for list slicing

  • 0

    Hey guys, wanted to share my python recursive solution. I didn't slice the list of nums in order to reduce space complexity, instead I used two pointers to track each half of the recursive call. The tricky bit is visiting each index only once, and knowing to return None if you get a wonky start / end pair index like 0,-1.

    class Solution(object):
        def sortedArrayToBST(self, nums):
            :type nums: List[int]
            :rtype: TreeNode
                return self.list2BST(0,len(nums)-1,nums)
        def list2BST(self,start,end,nums):
            mid = (start+end)/2
            k = TreeNode(nums[mid])
                return k
                return None
            k.left = self.list2BST(start,mid-1,nums)
            k.right= self.list2BST(mid+1,end,nums)
            return k 

Log in to reply

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