一、题目内容
题目要求根据一个不重复的整数数组 nums 构建最大二叉树。最大二叉树的构建规则如下：
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值左边的子数组前缀上构建左子树。
- 递归地在最大值右边的子数组后缀上构建右子树。
- 返回由
nums构建的最大二叉树。
二、题目分析
输入和输出
- 输入：一个不重复的整数数组
nums。 - 输出：构建好的最大二叉树的根节点（
TreeNode类型）。
递归函数 constructMaximumBinaryTree 的逻辑
- 基本情况：如果
nums的大小为 1，直接返回以该唯一元素为值的节点。 - 找到最大值：遍历
nums找到最大值及其索引。 - 创建根节点：以最大值创建根节点。
- 递归构建左子树：如果最大值左边有元素，递归构建左子树。
- 递归构建右子树：如果最大值右边有元素，递归构建右子树。
- 返回根节点：返回构建好的根节点。
三、代码解答
1.C++ 代码
class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {// 处理空数组的情况if (nums.empty()) return nullptr;// 基本情况：如果数组只有一个元素，直接返回该节点if (nums.size() == 1) return new TreeNode(nums[0]);// 初始化最大值和索引int maxvalue = nums[0];int index = 0;// 遍历数组找到最大值及其索引for (int i = 1; i < nums.size(); i++) {if (nums[i] > maxvalue) {maxvalue = nums[i];index = i;}}// 创建根节点TreeNode* node = new TreeNode(maxvalue);// 递归构建左子树：如果左边有元素if (index > 0) {// 提取左子数组：从开始到最大值索引之前的部分vector<int> vecleft(nums.begin(), nums.begin() + index);// 递归调用构建左子树node->left = constructMaximumBinaryTree(vecleft);}// 递归构建右子树：如果右边有元素if (index < nums.size() - 1) {// 提取右子数组：从最大值索引之后到结束的部分vector<int> vecright(nums.begin() + index + 1, nums.end());// 递归调用构建右子树node->right = constructMaximumBinaryTree(vecright);}// 返回根节点return node;}
};
2.详细注释
1.成员变量
TreeNode* constructMaximumBinaryTree(vector<int>& nums)：主函数，用于递归构建最大二叉树并返回根节点。
2.递归函数 constructMaximumBinaryTree
- 空数组检查：如果
nums为空，返回nullptr。 - 基本情况：如果
nums只有一个元素，直接返回以该元素为值的节点。 - 找到最大值：遍历
nums找到最大值及其索引。 - 创建根节点：以最大值创建根节点
node。 - 递归构建左子树：如果最大值左边有元素，提取左子数组并递归构建左子树。
- 递归构建右子树：如果最大值右边有元素，提取右子数组并递归构建右子树。
- 返回根节点：返回构建好的根节点
node。
3.回溯和递归的详细解释
1.递归
递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于逐步构建最大二叉树的每个子树。
- 递归调用：每次递归调用时，我们通过找到当前子数组的最大值确定当前子树的根节点，然后递归处理左子数组和右子数组。
- 终止条件：递归的终止条件是子数组为空或只有一个元素。
2.回溯
回溯是一种在递归调用返回后恢复状态的机制。在本题中，每次递归调用返回后，我们通过更新子数组的范围，恢复到当前子树的状态。这样可以确保每次递归返回后，状态正确，不会影响后续的递归调用。
4.示例
假设输入数组 nums = [3, 2, 1, 6, 0, 5]。
- 第一次调用：
- 最大值是 6，索引是 3。
- 创建根节点 6。
- 左子数组是
[3, 2, 1]，右子数组是[0, 5]。 - 递归构建左子树和右子树。
- 左子树构建：
- 子数组
[3, 2, 1]：- 最大值是 3，索引是 0。
- 创建节点 3。
- 左子数组为空，右子数组是
[2, 1]。 - 递归构建右子树。
- 子数组
- 右子树构建：
- 子数组
[0, 5]：- 最大值是 5，索引是 1。
- 创建节点 5。
- 左子数组是
[0]，右子数组为空。 - 递归构建左子树。
- 子数组
- 构建的最大二叉树为：
6
/ \
3 5
\ /
2 0
\
1
