力扣题解654：最大二叉树

一、题目内容

题目要求根据一个不重复的整数数组 nums 构建最大二叉树。最大二叉树的构建规则如下：

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值左边的子数组前缀上构建左子树。
3. 递归地在最大值右边的子数组后缀上构建右子树。
4. 返回由 nums 构建的最大二叉树。

二、题目分析

输入和输出

• 输入：一个不重复的整数数组 nums。
• 输出：构建好的最大二叉树的根节点（TreeNode 类型）。

递归函数 constructMaximumBinaryTree 的逻辑

1. 基本情况：如果 nums 的大小为 1，直接返回以该唯一元素为值的节点。
2. 找到最大值：遍历 nums 找到最大值及其索引。
3. 创建根节点：以最大值创建根节点。
4. 递归构建左子树：如果最大值左边有元素，递归构建左子树。
5. 递归构建右子树：如果最大值右边有元素，递归构建右子树。
6. 返回根节点：返回构建好的根节点。

三、代码解答

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

1. 空数组检查：如果 nums 为空，返回 nullptr。
2. 基本情况：如果 nums 只有一个元素，直接返回以该元素为值的节点。
3. 找到最大值：遍历 nums 找到最大值及其索引。
4. 创建根节点：以最大值创建根节点 node。
5. 递归构建左子树：如果最大值左边有元素，提取左子数组并递归构建左子树。
6. 递归构建右子树：如果最大值右边有元素，提取右子数组并递归构建右子树。
7. 返回根节点：返回构建好的根节点 node。

3.回溯和递归的详细解释

1.递归

递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于逐步构建最大二叉树的每个子树。

• 递归调用：每次递归调用时，我们通过找到当前子数组的最大值确定当前子树的根节点，然后递归处理左子数组和右子数组。
• 终止条件：递归的终止条件是子数组为空或只有一个元素。

2.回溯

回溯是一种在递归调用返回后恢复状态的机制。在本题中，每次递归调用返回后，我们通过更新子数组的范围，恢复到当前子树的状态。这样可以确保每次递归返回后，状态正确，不会影响后续的递归调用。

4.示例

假设输入数组 nums = [3, 2, 1, 6, 0, 5]。

1. 第一次调用：
   • 最大值是 6，索引是 3。
   • 创建根节点 6。
   • 左子数组是 [3, 2, 1]，右子数组是 [0, 5]。
   • 递归构建左子树和右子树。
2. 左子树构建：
   • 子数组 [3, 2, 1]：
     • 最大值是 3，索引是 0。
     • 创建节点 3。
     • 左子数组为空，右子数组是 [2, 1]。
     • 递归构建右子树。
3. 右子树构建：
   • 子数组 [0, 5]：
     • 最大值是 5，索引是 1。
     • 创建节点 5。
     • 左子数组是 [0]，右子数组为空。
     • 递归构建左子树。
4. 构建的最大二叉树为：

      6
     / \
    3   5
     \  /
      2 0
       \
        1