Maximum Binary Tree

Problem Statement

Given an integer array nums without any duplicates, the task is to construct a maximum binary tree based on specific rules. The construction of the tree is defined recursively:

1. Identify the maximum element in the array nums and make it the root node of the binary tree.
2. Treat the elements to the left of this maximum value as a subarray and recursively repeat the process to build the left subtree.
3. Similarly, take the elements to the right of the maximum value as another subarray and recursively construct the right subtree.

The resulting structure should be a binary tree where each node is the maximum value of its respective subarray.

Examples

Example 1

Input:

nums = [3,2,1,6,0,5]

Output:

[6,3,5,null,2,0,null,null,1]

Explanation:

The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
- Empty array, so no child.
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.

Example 2

Input:

nums = [3,2,1]

Output:

[3,null,2,null,1]

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• All integers in nums are unique.

Approach and Intuition

Based on the examples and constraints provided, the approach involves repeatedly finding the maximum element in the current subarray to establish tree nodes:

1. Start by identifying the maximum element in the initial full array. This forms your root node.

   • For nums = [3,2,1,6,0,5], the root is 6.

2. Divide the array around the root node into two sections:

   • Left of the maximum for left subtree.
   • Right of the maximum for right subtree.

3. Apply the same logic recursively:

   • For the left subarray [3,2,1] relative to 6, the maximum 3 becomes the left child.
   • Continue subdividing [3,2,1] into [] on the left of 3 and [2,1] on the right.

4. Process each subtree similarly:

   • For [2,1], 2 is the maximum and 1 falls on the right of 2.

5. For arrays reduced to single elements like [0] and [5] in the example, they become leaf nodes directly.

6. The process includes many recursive calls:

   • Each recursive call handles a progressively smaller subarray until the entire array is processed into the tree structure.

By recursive decomposition of the input based on maximum values and treating them as roots, we build the maximum binary tree efficiently, respecting the constraints set forth (up to 1000 elements, each unique between 0 and 1000). Thus, each step focuses on locating the maximum, using it as a root, and partitioning the rest for further recursive structuring into a coherent maximum binary tree.

Solutions

public class Solution {
    public TreeNode buildMaxBinaryTree(int[] elements) {
        return buildTree(elements, 0, elements.length);
    }
    public TreeNode buildTree(int[] elements, int left, int right) {
        if (left == right)
            return null;
        int maxIndex = findMaxIndex(elements, left, right);
        TreeNode node = new TreeNode(elements[maxIndex]);
        node.left = buildTree(elements, left, maxIndex);
        node.right = buildTree(elements, maxIndex + 1, right);
        return node;
    }
    public int findMaxIndex(int[] elements, int left, int right) {
        int indexOfMax = left;
        for (int i = left; i < right; i++) {
            if (elements[indexOfMax] < elements[i])
                indexOfMax = i;
        }
        return indexOfMax;
    }
}