654. 最大二叉树

654. 最大二叉树

难度中等323 收藏 分享 切换为英文 接收动态 反馈

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

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

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

思路：递归调用，查找最大的元素作为二叉树的头

代码：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode head = findMaxTreeNode(nums,0,nums.length);
        return head;
    }
    public TreeNode findMaxTreeNode(int[] nums,int l,int r){
        if(l==r)return null;
        int maxNum = l;
        int i = l;
        while(i<r){
            if(nums[maxNum]<nums[i]){
                maxNum = i;
            }
            i++;
        }
        TreeNode newHead = new TreeNode(nums[maxNum]);
        newHead.left = findMaxTreeNode(nums,l,maxNum);
        newHead.right = findMaxTreeNode(nums,maxNum+1,r);
        return newHead;
    }
}