二叉树 最大二叉树654（中等）

需求：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
示例1：

二叉树

示例：2

二叉树

注意：

遍历方式：构造二叉树类，都是使用前序遍历，先创建出中再去递归构造左右子树。

概念：

取数组中最大的元素作为根节点，数组左区间作为左子树，数组右区间作为右子树。根据以上规则继续向下层递归创建。

leetcode题目链接

思路

了解了最大二叉树的概念直接根据概念进行数组切分，创建数据返回就可以了。

/**
 * 654. 最大二叉树
 */
public class ConstructMaximumBinaryTree654 {
    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length < 1) return null;
        // 数组只有一个元素创建直接返回
        if(nums.length == 1) return new TreeNode(nums[0]);
        int indexMax = 0;
        int valueMax = 0;

        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        // 双指针法：获取当前数组最大值
        while (leftIndex <= rightIndex) {
            if (nums[leftIndex] > nums[rightIndex]) {
                if(nums[leftIndex]>valueMax){
                    indexMax = leftIndex;
                    valueMax = nums[leftIndex];
                }
                leftIndex++;
            } else {
                if(nums[rightIndex]>valueMax){
                    indexMax = rightIndex;
                    valueMax = nums[rightIndex];
                }
                rightIndex--;
            }
        }
//        // 单循环获取最大值
//        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(valueMax); // 中
        root.left = constructMaximumBinaryTree(Arrays.copyOf(nums, indexMax)); // 左
        int rightLength = nums.length - indexMax - 1;
        int[] rightArray = new int[rightLength];
        System.arraycopy(nums, indexMax + 1, rightArray, 0, rightLength);
        root.right = constructMaximumBinaryTree(rightArray); // 右

        return root;
    }

    public static void main(String[] args) {
        int[] root = new int[]{3,2,1,6,0,5};
        constructMaximumBinaryTree(root);
    }
}

验证结果