Skip to main content

Maximum Binary Tree

Question​

Given an integer array with no duplicates, construct a maximum binary tree containing values from the array. Return the root node of the maximum binary tree.

Example 1
Input: [3,2,1,6,0,5]
Output: 
      6
    /   \
   3     5
  / \    /
 2   1  0

Solution​

all//Maximum Binary Tree.py


# Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

# The root is the maximum number in the array
# The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
# The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

# Construct the maximum tree by the given array and output the root node of this tree.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def constructMaximumBinaryTree(nums):
    if not nums:
        return None
    # Find the max value and its index
    maxVal, maxIndex = float('-inf'), 0
    for i, n in enumerate(nums):
        if n > maxVal:
            maxVal, maxIndex = n, i
    # Create the root node with the max value
    root = TreeNode(maxVal)
    # Create the left and right subtrees recursively
    root.left = constructMaximumBinaryTree(nums[:maxIndex])
    root.right = constructMaximumBinaryTree(nums[maxIndex+1:])
    return root