Recursive Python solution, no extra space used for list slicing


  • 0
    J

    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
            """
            if(nums): 
                return self.list2BST(0,len(nums)-1,nums)
            
            
        def list2BST(self,start,end,nums):
            mid = (start+end)/2
            
            k = TreeNode(nums[mid])
            if(start==end):
                return k
            if(start>end):
                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.