Iterative solution in python


  • 2
    G

    In case anyone was wondering what an iterative solution looks like in python, here is one. Around 100ms, so apparently not any faster than a recursive solution - probably due to the extra if's needed to make it work. No pointers or references make this somewhat tricky and less efficient than it could be with them.

    class Solution(object):    
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums:
            return None
        lb=0
        ub=len(nums)
        middle = ub>>1
        root = TreeNode(nums[middle])
        walker = root
        if ub - middle > 1:
            rights = [(root,middle+1,ub)]
        else:
            rights = []
        ub=middle
        while 1:
            diff = ub-lb
            if diff:
                middle = lb+(diff>>1)
                walker.left = TreeNode(nums[middle])
                walker = walker.left
            elif rights:
                walker,lb,ub = rights.pop()
                diff = ub-lb
                middle = lb+(diff>>1)
                walker.right = TreeNode(nums[middle])
                walker = walker.right
            else:
                break
            if ub - middle > 1:
                rights.append((walker,middle+1,ub))
            ub=middle
            
        return root

Log in to reply
 

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