Maximum Binary Tree - Leetcode Solution

The Maximum Binary Tree problem on LeetCode requires us to construct a binary tree from an array of integers such that the root node has the maximum value in the array, and the left subtree and right subtree are constructed recursively with the subarrays to the left and right of the maximum element, respectively.

Here is a detailed solution to this problem using a recursive approach:

1. First, we need to find the maximum element in the array and its index. We can use a linear search to find the maximum element and its index.

2. Once we have the maximum element, we can create a new node with the maximum value and assign it as the root node of the tree.

3. We can then recursively construct the left and right subtrees, passing in the subarrays to the left and right of the maximum element, respectively.

4. To construct the left subtree, we can call our function recursively with the subarray from the start of the input array up to the index of the maximum element.

5. To construct the right subtree, we can call our function recursively with the subarray from the index of the maximum element plus one to the end of the input array.

6. Finally, we can return the root node of the tree.

Here is the Python code for the above approach:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def constructMaximumBinaryTree(nums):
    if not nums:
        return None
    
    # Find index of maximum element
    max_idx = 0
    for i in range(len(nums)):
        if nums[i] > nums[max_idx]:
            max_idx = i
    
    # Create new node with maximum value as root node
    root = TreeNode(nums[max_idx])
    
    # Recursively construct left and right subtrees
    root.left = constructMaximumBinaryTree(nums[:max_idx])
    root.right = constructMaximumBinaryTree(nums[max_idx+1:])
    
    return root

Time Complexity: O(n^2), where n is the length of the input array. This is because we are using a linear search to find the maximum element, which takes O(n) time, and we are calling the function recursively for each subarray, which can take up to O(n) time in the worst case if the array is already sorted.

Space Complexity: O(n), where n is the length of the input array. This is because we are creating a new node for each element in the input array.

1