654. 最大二叉树
难度中等323 收藏 分享 切换为英文 接收动态 反馈
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
- 二叉树的根是数组
nums中的最大元素。 - 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 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;
}
}
