这段Java代码实现了一个名为Solution的类,其中包含两个方法:constructMaximumBinaryTree()和constructMaximumBinaryTree1(),目的是从给定的整数数组nums中构建出一个最大二叉树。以下是详细的注释说明:
class Solution {
// 主方法,接收一个整数数组nums作为输入参数,调用辅助递归方法constructMaximumBinaryTree1(),
// 传入整个数组以及对应的首尾索引(默认从0开始到数组长度)
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree1(nums, 0, nums.length);
}
// 辅助递归方法,负责实际构建最大二叉树的过程
// 参数包括:
// nums:输入的整数数组
// leftIndex:子数组的起始索引
// rightIndex:子数组的结束索引(不包含)
public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
// 当子数组为空(没有元素),直接返回null表示没有树节点
if (rightIndex - leftIndex < 1) {
return null;
}
// 当子数组仅有一个元素时,创建一个新的TreeNode,以其值作为节点值并返回
if (rightIndex - leftIndex == 1) {
return new TreeNode(nums[leftIndex]);
}
// 寻找子数组中的最大值及其索引
int maxIndex = leftIndex; // 初始假设最大值位于子数组的第一个元素
int maxVal = nums[maxIndex]; // 初始化最大值等于第一个元素值
for (int i = leftIndex + 1; i < rightIndex; i++) {
// 遍历子数组,如果找到更大的值,则更新最大值及其索引
if (nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
// 使用找到的最大值创建一个新的TreeNode作为子树的根节点
TreeNode root = new TreeNode(maxVal);
// 递归构建左右子树
// 左子树由原始数组在[leftIndex, maxIndex)范围内的元素构成
root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
// 右子树由原始数组在[maxIndex+1, rightIndex)范围内的元素构成
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
// 返回已构建好的以最大值为根节点的子树
return root;
}
}
// TreeNode是一个自定义的树节点类,通常包含一个整数值val以及指向左右子树的引用left和right
这个算法的核心思想是每次都选择子数组中的最大值作为当前子树的根节点,然后递归地对剩余部分数组构建左右子树,确保任何节点在它的子树中都具有最大的值。最后,这个过程会构建出一颗所有路径上节点值都递增的二叉树,且任意节点的值均大于其左右子节点的值。