Similar Problems
Similar Problems not available
Maximum Binary Tree  Leetcode Solution
Companies:
LeetCode: Maximum Binary Tree Leetcode Solution
Difficulty: Medium
Topics: stack tree binarytree array
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:

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.

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.

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

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.

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.

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.
Maximum Binary Tree Solution Code
1