The maximum binary tree could be constructed recurisivly.
# 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