654. 最大二叉树

示例 1：

示例 2：

输入：nums = [3,2,1] 输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

递归

```java /**

Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}

} */ class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) {

/**
递归：
确定递归函数的参数和返回值
    参数就是传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针
确定终止条件
    题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
    那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
确定单层递归的逻辑
    这里有三步工作
        1.先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
        2.最大值所在的下标左区间 构造左子树
            这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值。
        3.最大值所在的下标右区间 构造右子树
        判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值。
https://www.programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#java
 */
return constructMaximumBinaryTree(nums,0,nums.length);

}

public TreeNode constructMaximumBinaryTree(int[] nums,int left,int right ) {

if(right - left < 1 ) return null;
if(right - left == 1 ) return new TreeNode(nums[left]);

int maxValue = Integer.MIN_VALUE;
int maxIndex = left;

for(int i = left; i < right; i++ ) {
    if(nums[i] > maxValue) {
        maxValue = nums[i];
        maxIndex = i;
    }
}

TreeNode root = new TreeNode(maxValue);
root.left = constructMaximumBinaryTree(nums,left,maxIndex);
root.right = constructMaximumBinaryTree(nums,maxIndex + 1,right);

return root;

} }

```