leetcode最大二叉树

在本题中，我们是要将给定的数组构成一个二叉树，其根节点是数组中最大的元素，左子树都是最大值左边元素组成的，右子树都是最大值右边元素组成的。所以本题的关键在于我们先需要找到最大的元素。
我们构造二叉树，一般是采用前序的遍历顺序（中左右）。我们采用递归的方式，
递归三部曲：
首先确定我们需要的是函数的参数以及返回值，我们需要将数组传入，同时为了确保层层递归构建树，我们需要一个左边起始索引，右边起始索引。返回值应该是treenode类型。
其次我们确定递归截至条件。当我们的左右索引相差小于1的时候，证明二者走到了一起，这个时候我们直接返回null就可以了。如果二者相差正好等于1，说明此时只有一个节点就是根节点，直接返回新建的节点即可。
最后我们确定单层递归的逻辑。我们首先要找到数组中的最大值。然后按照遍历顺序，中左右，首先建立起根节点，然后再递归根节点的左子树，再递归根节点的右子树即可。

class Solution {
    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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27