Python Solution, recursive and no recursive


  • 0
    G

    Recursive Solution

    class Solution:
        def constructMaximumBinaryTree(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            if 0 == len(nums):
                return None
            root = TreeNode(0)
            n = 0
            for i in range(len(nums)):
                if nums[n] < nums[i]:
                    n = i
            root.val = nums[n]
            root.left = self.constructMaximumBinaryTree(nums[:n])
            root.right = self.constructMaximumBinaryTree(nums[n + 1:])
    
            return root
    

    No Recursive Solution

    class Solution:
        def constructMaximumBinaryTree(self, nums):
            if 0 == len(nums):
                return None
            root = TreeNode(nums[0])
            for num in nums[1:]:
                # no duplicates
                if num < root.val:
                    if not root.right:
                        root.right = TreeNode(num)
                    else:
                        # find the position
                        t = root
                        while t.right and t.right.val > num:
                            t = t.right
                        if not t.right:
                            t.right = TreeNode(num)
                        else:
                            t2 = t.right
                            t.right = TreeNode(num)
                            t.right.left = t2
                else:
                    t = TreeNode(num)
                    t.left = root
                    root = t
    
            return root
    

Log in to reply
 

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