10 lines O(n), python using stack

  • 0

    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
    	return dummy.right

Log in to reply

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