# 654. Maximum Binary Tree

## Problem Statement

<br>

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`.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg)

<pre><code><strong>Input: nums = [3,2,1,6,0,5]
</strong><strong>Output: [6,3,5,null,2,0,null,null,1]
</strong><strong>Explanation: The recursive calls are as follow:
</strong>- 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.
</code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/12/24/tree2.jpg)

<pre><code><strong>Input: nums = [3,2,1]
</strong><strong>Output: [3,null,2,null,1]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 1000`
* All integers in `nums` are **unique**.<br>

## Intuition

```
Here, we recursively build the tree, Divide into left
and right sub-tree

Find the maximum and build
```

### Links

<https://leetcode.com/problems/maximum-binary-tree/description/>

### Video Links

### Approach 1:

```
Recursion
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    TreeNode* find_ans(vector<int>& nums, int i, int j){
        if(i>j)
            return nullptr;

        int index = helper(nums, i, j);
        TreeNode *root = new TreeNode(nums[index]);

        root->left = find_ans(nums, i, index-1);
        root->right = find_ans(nums, index+1, j);

        return root;
    }

    int helper(vector<int>& nums, int i, int j){
        int idx = 0;
        int maxi = 0;

        for(int index=i; index<=j; index++){
            if(maxi <= nums[index]){
                maxi = nums[index];
                idx = index;
            }
        }

        return idx;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int i=0;
        int j=nums.size()-1;

        return find_ans(nums, i, j);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###