上一期我们总结了二叉树的递归遍历方法,其实二叉树的很多题目都涉及到了递归。
因为递归的思想,用同样的逻辑去完成不同节点的构建就很符合二叉树的数据结构,今天我们就来看另一道与递归有关的二叉树题,希望能让你加深印象。
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:
二叉树的根是数组 nums 中的最大元素。左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。返回有给定数组 nums 构建的 最大二叉树 。
示例 1:
输入:nums = [3,2,1,6,0,5] 输出:[6,3,5,null,2,0,null,null,1] 解释:递归调用如下所示:
题意还是比较简单的,示例中也具体说明了。
就是找到数组中最大的数字作为根节点,然后将最大数字两边的数组继续构建成左右子树即可,所以我们可以按照题意写一段伪代码:
Tree buildTreebyFindMax(int[] nums , int leftIndex, int rightIndex){
//找到最大值的下标
int maxIndex = findMax(nums);
//构建根节点为最大值的树
TreeNode root = new TreeNode(nums[maxIndex]);
//递归获取左子树
root.left = buildTreebyFindMax(nums,leftIndex, maxNum);
//递归获取右子树
root.right = buildTreebyFindMax(nums, maxNum+1, rightIndex);
return root;
}
只要给定每次递归中的左限定节点后右限定节点,就可以找到这个限定范围内 数组的最大值,然后作为一个根节点构建子树。
最后递归完成
,树的构建就完成了。
梳理之后,我们要解决的主要问题就是,这个findMax
,找到最大值方法该怎么实现呢?
很简单,有数组,也有开始和结束节点,那我们遍历数组就可以找到最大值了,为了方便下一次递归方法的使用,我们直接返回最大值的下标即可:
public int findMax(int[] nums, int l, int r) {
int max = l;
for (int i = l; i < r; i++) {
if (nums[max] < nums[i])
max = i;
}
return max;
}
还有一个问题需要解决,就是递归方法的终止条件
,什么时候停止递归呢?
比如:[3,2,1]
所以终止条件其实就是leftIndex = rightIndex
,区间数组为空的时候。
if (l == r)
return null;
最后的解法完整版如下:
public class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length);
}
public TreeNode construct(int[] nums, int l, int r) {
if (l == r)
return null;
int max = findMax(nums, l, r);
TreeNode root = new TreeNode(nums[max]);
root.left = construct(nums, l, max);
root.right = construct(nums, max + 1, r);
return root;
}
public int findMax(int[] nums, int l, int r) {
int max = l;
for (int i = l; i < r; i++) {
if (nums[max] < nums[i])
max = i;
}
return max;
}
}
时间复杂度:O(n^2) 空间复杂度:O(n)
https://leetcode-cn.com/problems/maximum-binary-tree
感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—
码上积木
❤️ 每日一个知识点,建立完整体系架构。