leetcode-654 最大二叉树

题目描述：给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：

• 二叉树的根是数组 nums 中的最大元素。
• 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
• 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

返回有给定数组 nums 构建的 最大二叉树 。

代码实现

递归实现

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

    public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
        //1. 判空
        if (start >= end) {
            return null;
        }

        //2. 单个元素直接返回
        if (start == end - 1) {
            TreeNode node = new TreeNode(nums[start]);
            return node;
        }

        //3. 寻找最大元素
        int maxVal = nums[start];
        int maxIdx = start;
        for (int idx = start; idx < end; idx++) {
            if (nums[idx] > maxVal) {
                maxVal = nums[idx];
                maxIdx = idx;
            }
        }

        //4. 最大元素为根节点
        TreeNode root = new TreeNode(maxVal);

        //5. 最大元素左边为左子树
        TreeNode leftNode = constructMaximumBinaryTree(nums, start, maxIdx);

        //6. 最大元素右边为右子树
        TreeNode rightNode = constructMaximumBinaryTree(nums, maxIdx + 1, end);

        //7. 连接左右子树
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}