Maximum Binary Tree

Intuition

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        return self._helper(nums, 0, len(nums) - 1)

    def _helper(self, nums, lo, hi):
        if hi < lo:
            return None
        m, m_i = nums[lo], lo
        for i in range(lo, hi + 1):
            if nums[i] > m:
                m, m_i = nums[i], i
        node = TreeNode(m)
        node.left = self._helper(nums, lo, m_i - 1)
        node.right = self._helper(nums, m_i + 1, hi)
        return node