二叉树第五天！开始上难度了。w_w

题目链接：654. 最大二叉树

状态：不太会，甚至连递归里选用前中后序其中的哪个都不知道。果断直接看解析。最后是做到了AC。

解析部分：构造树一般采用的是前序遍历，因为要先构造中间节点，然后才递归构造左右子树。

1. 确定递归函数的参数和返回值。参数传入的是存放元素的数组，返回该数组结构的二叉树的头节点，返回类型是指向节点的指针。
   之所以这样设计是因为我们要在确定完中间节点之后，把原数组拆分为子数组，往递归里传。

2. 确定终止条件。因为由题目已知输入的数组是大于等于1的，所以不用考虑小于1的情况。因此当遍历时如果发现数组大小为1，则证明遍历到叶子节点了。所以此时应该定义一个新的节点并把数组的值赋值给它。然后返回这个节点。

3. 确定单层递归逻辑。这里有三步要做：

• 先要找到数组中最大的值和对应的下标，最大的值用来构造根节点，下标用来切割数组。
• 在最大值所在下标的左区间 构造左子树
• 在最大值所在下标的右区间 构造右子树

完整代码如下：

class Solution { // Java
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}

复杂度分析：
时间复杂度：O(n^2). 寻找最大值的时间复杂度初始为O(n)，随后数组被分为左右两部分，再寻找最大值时需要O(k)时间，k是当前范围大小。所以最坏情况下是数组为已排序的数组，时间复杂度为O(n + (n-1) + (n-2) + ... + 1) = O(n^2).
空间复杂度：O(n). 最坏情况下，数组为单调数组，所以递归调用栈的高度等于数组大小n，因此在此情况下空间复杂度为O(n)， 其他空间消耗都是常数，所以综合下来空间复杂度为O(n).