10 lines O(n), python using stack


  • 0
    S

    A python implement of an O(n) solution using stack, which is already known by many. The dummy node may not be necessary, but it makes the stack non-empty.

    def constructMaximumBinaryTree(self, nums):
    
    	dummy = TreeNode(sys.maxint)
    	stack = [dummy]
    	for num in nums:
    		node = TreeNode(num)
    		while stack[-1].val < num:
    			node.left = stack.pop()
    		stack[-1].right = node
    		stack.append(node)
    	return dummy.right
    

Log in to reply
 

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