Leetcode 654.最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 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] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
解题思路：
当解析这道题的解题思路时，需要注意到以下几点：
- 我们需要构建一个二叉树，该二叉树的每个节点的值都是给定数组中的某个元素。
- 数组中的最大值将成为根节点，而根节点的左子树将由数组中的较大值构成，根节点的右子树将由数组中的较小值构成。
- 我们可以使用递归来构建二叉树，递归函数的参数包括数组、当前子树的起始索引和结束索引，以及一个哈希映射用于快速查找每个数值对应的索引。
下面是详细的解题思路：
- 首先，我们需要处理特殊情况。如果给定的数组为空或长度为0，则直接返回空树。
- 创建一个哈希映射（HashMap），用于快速查找每个数值在数组中的索引。遍历数组，将每个数值及其索引存入哈希映射中。
- 调用递归函数
buildTree，传入数组、起始索引、结束索引和哈希映射。该函数将返回以当前子数组构建的二叉树。 - 在
buildTree函数中，首先判断起始索引是否大于结束索引。如果是，表示当前子数组为空，返回 null，表示空树。 - 否则，我们需要找到当前子数组中的最大值。调用
getMaxNode函数，传入数组和起始、结束索引，该函数将返回当前子数组中的最大值。 - 使用哈希映射获取最大值在原始数组中的索引。这个索引将用于分割左右子数组。
- 创建一个树节点，节点的值为当前最大值。
- 递归调用
buildTree函数构建左子树，传入数组、起始索引和最大值索引减1的结束索引。这样可以构建该节点的左子树，包含了较大的值。 - 递归调用
buildTree函数构建右子树，传入数组、最大值索引加1的起始索引和结束索引。这样可以构建该节点的右子树，包含了较小的值。 - 将构建好的左右子树分别赋值给当前节点的
left和right属性。 - 返回当前构建好的树节点。
- 最后，递归结束后，返回构建好的二叉树。
总结一下，该算法的核心思想是利用递归和哈希映射来构建最大二叉树。通过划分子数组、查找最大值和递归构建子树的过程，逐步构建出完整的二叉树结构。
代码实现：
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if(nums == null || nums.length == 0){
return null;
}
// 记录当前的最大值
int max = 0;
// 创建一个 HashMap 用于快速查找每个数值对应的索引
HashMap<Integer,Integer> hashMap = new HashMap();
// 将每个数值及其索引存入 HashMap
for(int i = 0;i < nums.length;i++){
hashMap.put(nums[i],i);
}
// 调用 buildTree 方法构建最大二叉树
return buildTree(nums,0,nums.length-1,hashMap);
}
public TreeNode buildTree(int[] nums,int start,int end,HashMap<Integer,Integer> hashMap){
// 当起始索引大于结束索引时，返回 null，表示当前子树为空
if(start > end ){
return null;
}
// 获取当前范围内的最大值
int maxNode = getMaxNode(nums,start,end);
// 获取当前最大值在原始数组中的索引
int maxIndex = hashMap.get(maxNode);
// 创建根节点，值为当前最大值
TreeNode treeNode = new TreeNode(maxNode);
// 递归构建左子树，范围为起始索引到当前最大值索引的前一个位置
treeNode.left = buildTree(nums,start,maxIndex-1,hashMap);
// 递归构建右子树，范围为当前最大值索引的后一个位置到结束索引
treeNode.right = buildTree(nums,maxIndex+1,end,hashMap);
// 返回当前构建的树
return treeNode;
}
public int getMaxNode(int[] nums,int start,int end){
// 初始化最大值为整数最小值
int max = Integer.MIN_VALUE;
for(int i = start;i <= end;i++){
if(nums[i] > max){
// 更新最大值
max = nums[i];
}
}
// 返回最大值
return max;
}
}
评论区