654. 最大二叉树
难度中等给定一个不重复的整数数组 nums
。 最大二叉树 可以用下面的算法从 nums
递归地构建:
- 创建一个根节点,其值为
nums
中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums
构建的 最大二叉树 。
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public TreeNode constructMaximumBinaryTree(int[] nums) { 18 return tree(nums,0,nums.length-1); 19 } 20 21 public TreeNode tree(int[] nums,int l,int r){ 22 if (l>r) return null; 23 int max=-1,index=-1; 24 for (int i=l;i<=r;i++){ 25 if (nums[i]>max){ 26 max=nums[i]; 27 index=i; 28 } 29 } 30 TreeNode root=new TreeNode(max); 31 root.left=tree(nums,l,index-1); 32 root.right=tree(nums,index+1,r); 33 return root; 34 } 35 }
思路:给出数组的上下界递归调用。
标签:right,TreeNode,val,nums,int,二叉树,2022,20 From: https://www.cnblogs.com/benbicao/p/16607313.html