654. Maximum Binary Tree (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        # recursion O(n^2)
        if nums:
            m = max(nums)
            i = nums.index(m)
            root = TreeNode(
                val = m,
                left = self.constructMaximumBinaryTree(nums[ : i]),
                right = self.constructMaximumBinaryTree(nums[i + 1 : ])
            )
            return root
    
        # stack O(n)
        stack = []
        for num in nums:
            node = TreeNode(num)
            while stack and num > stack[-1].val:
                node.left = stack.pop()
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]