## Algorithm

Problem Name: 654. Maximum Binary Tree

You are given an integer array `nums` with no duplicates. A maximum binary tree can be built recursively from `nums` using the following algorithm:

1. Create a root node whose value is the maximum value in `nums`.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from `nums`.

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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector& nums) {
return DFS(nums, 0, nums.size());
}

TreeNode* DFS(vector& nums, int l, int r){
if(l == r) return NULL;
int maxPos = l;
for(int i = l; i < r; i++) if(nums[i] > nums[maxPos]) maxPos = i;
TreeNode* root = new TreeNode(nums[maxPos]);
root->left = DFS(nums, l, maxPos);
root->right = DFS(nums, maxPos + 1, r);
return root;
}
};

// O(n)
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector& nums) {
dequeq;
for(auto x: nums){
TreeNode* p = new TreeNode(x);
while(!q.empty() && q.back()->val < x) p->left = q.back(), q.pop_back();
if(!q.empty() && q.back()->val > x) q.back()->right = p;
q.push_back(p);
}
return q.front();
}
};
``````
Copy The Code &

Input

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

Output

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

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length == 0) {
return null;
}
TreeNode root = helper(nums, 0, nums.length - 1);
return root;
}

private TreeNode helper(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int maxIdx = getMaxIdx(nums, start, end);
TreeNode root = new TreeNode(nums[maxIdx]);
root.left = helper(nums, start, maxIdx - 1);
root.right = helper(nums, maxIdx + 1, end);
return root;
}

private int getMaxIdx(int[] nums, int start, int end) {
int maxVal = Integer.MIN_VALUE;
int maxIdx = -1;
while (start <= end) {
if (nums[start] > maxVal) {
maxVal = nums[start];
maxIdx = start;
}
start++;
}
return maxIdx;
}
}
``````
Copy The Code &

Input

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

Output

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

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums:
pos = nums.index(max(nums))
root = TreeNode(nums[pos])
root.left = self.constructMaximumBinaryTree(nums[:pos])
root.right = self.constructMaximumBinaryTree(nums[pos+1:])
return root
``````
Copy The Code &

Input

cmd
nums = [3,2,1]

Output

cmd
[3,null,2,null,1]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0654_MaximumBinaryTree
{
public TreeNode ConstructMaximumBinaryTree(int[] nums)
{
return ConstructMaximumBinaryTree(nums, 0, nums.Length);
}

private TreeNode ConstructMaximumBinaryTree(int[] nums, int left, int right)
{
if (left == right) return null;
var maxIndex = GetMaxIndex(nums, left, right);

var node = new TreeNode(nums[maxIndex]);
node.left = ConstructMaximumBinaryTree(nums, left, maxIndex);
node.right = ConstructMaximumBinaryTree(nums, maxIndex + 1, right);

return node;
}

private int GetMaxIndex(int[] nums, int left, int right)
{
var result = left;
for (int i = left; i < right; i++)
if (nums[result] < nums[i]) result = i;

return result;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [3,2,1]

Output

cmd
[3,null,2,null,1]