Python O(N) using Stack


  • 0
    D

    Inspired by @votrubac and @Mrsuyi
    https://discuss.leetcode.com/topic/98454/c-9-lines-o-n-log-n-map
    https://discuss.leetcode.com/topic/98509/c-o-n-solution

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def constructMaximumBinaryTree(self, nums):
            """
            :type nums: List[int]
            :rtype: TreeNode
            """
            stk = []
            for i in range(len(nums)):
                cur = TreeNode(nums[i])
                l = None
                while stk!=[] and stk[-1].val < nums[i]:
                    l = stk[-1]
                    stk.pop()
                cur.left = l
                if stk!=[]:
                    stk[-1].right = cur
                stk.append(cur)
            return stk[0]
    

  • 0

    Just translated your code to Python:

    def constructMaximumBinaryTree(self, nums):
        stk = []
        for num in nums:
            cur = TreeNode(num)
            while stk and stk[-1].val < num:
                cur.left = stk.pop()
            if stk:
                stk[-1].right = cur
            stk.append(cur)
        return stk[0]
    

    And for extra fun:

    def constructMaximumBinaryTree(self, nums):
        stk = [TreeNode(math.inf)]
        for num in nums:
            cur = TreeNode(num)
            while stk[-1].val < num:
                cur.left = stk.pop()
            stk[-1].right = cur
            stk.append(cur)
        return stk[1]

Log in to reply
 

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