企业网站建设 优化,潍坊建设公司,网站做了泛解析 为什么影响seo,网站运营新手做题目#xff1a;
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点#xff0c;其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums…题目
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
思路递归法。
第一步确定参数与返回值。参数为nums数组要遍历区域的起始下标beginIndex终止下标endIndex区间左闭右开返回值为树。
第二步确定终止条件。当endIndex-beginIndex1时说明数组里无元素返回null
第三步确定单层递归逻辑。当endIndex-beginIndex1说明数组里只有一个元素为该元素创建一个新节点当endIndex-beginIndex1时遍历数组找到最大元素的值与下标创建节点root存储该元素递归root.left与root.right。
代码
public TreeNode constructMaximumBinaryTree(int[] nums) {return construct(nums,0,nums.length);}public TreeNode construct(int[] nums,int beginIndex,int endIndex){if(endIndex-beginIndex1) return null;//没有元素了if(endIndex-beginIndex1) return new TreeNode(nums[beginIndex]);//只有一个元素int maxIndexbeginIndex;//最大值下标int maxValnums[beginIndex];//最大值for(int ibeginIndex1;iendIndex;i){if(nums[i]maxVal){maxIndexi;maxValnums[i];}}//寻找最大值及下标TreeNode rootnew TreeNode(maxVal);root.leftconstruct(nums,beginIndex,maxIndex);root.rightconstruct(nums,maxIndex1,endIndex);return root;}
