Problem statement

https://leetcode.com/problems/maximum-binary-tree/

Solution

Straightforward solution is to use recursion: just do what is asked.

Complexity

Time complexity is O(nh), space is O(n).

Code

class Solution:
    def constructMaximumBinaryTree(self, nums):
        if not nums: return None
        idx = nums.index(max(nums))
        root = TreeNode(nums[idx])
        root.left = self.constructMaximumBinaryTree(nums[:idx])
        root.right = self.constructMaximumBinaryTree(nums[idx+1:])
        return root

Solution 2

Actually, what is asked to construct is Cartesian tree. There is also smart solution, using decreasing stack with O(n) time/space complexity - the idea is that for each element num its left children is the biggest element to the left, smaller than num and its right children is the biggest element to the right, smaller than num.

Complexity

Time complexity is O(n), space is O(n).

Code

class Solution:
    def constructMaximumBinaryTree(self, nums):
        stack = [TreeNode(float('inf'))]
        for num in nums:
            node = TreeNode(num)
            while stack[-1].val < num:
                node.left = stack.pop()
            stack[-1].right = node
            stack.append(node)
        return stack[0].right

Remark

Another solution is to use BIT or segment tree to quick access to maximum in range with complexity O(n log n).