# Python O(N) using Stack

• ``````# 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]
``````

• 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]``````

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