LeetCode题解—最大二叉树
上一期我们总结了二叉树的递归遍历方法，其实二叉树的很多题目都涉及到了递归。
因为递归的思想，用同样的逻辑去完成不同节点的构建就很符合二叉树的数据结构，今天我们就来看另一道与递归有关的二叉树题，希望能让你加深印象。
题目:最大二叉树
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums 中的最大元素。左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。返回有给定数组 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1] 解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
分析
题意还是比较简单的，示例中也具体说明了。
就是找到数组中最大的数字作为根节点，然后将最大数字两边的数组继续构建成左右子树即可，所以我们可以按照题意写一段伪代码：
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=0，rightIndex=3，然后找到最大数组3。
- 所以下一步递归方法中传入的leftIndex=0，rightIndex=0，区间数组为空，返回。
所以终止条件其实就是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
感谢大家的阅读，有一起学习的小伙伴可以关注下公众号—
码上积木❤️ 每日一个知识点，建立完整体系架构。