力扣第654题：最大二叉树解题教程 用数组构造最大二叉树

题目解读

给定一个不含重复元素的整数数组，我们需要构建一棵最大二叉树。构建规则是：数组中的最大值作为根节点，其左侧子数组构建左子树，右侧子数组构建右子树，然后递归地应用这个规则。这种构建方式体现了分治思想，将大问题分解为小问题来解决，最终组合成完整的解决方案。

解题思路与过程

用递归和分治的方法来构建最大二叉树。定义一个辅助函数maxbinarytree来处理子数组的构建过程。当子数组为空时返回空指针，否则找到当前子数组的最大值作为根节点值，并记录其索引位置。然后递归构建左子树（使用最大值左侧的子数组）和右子树（使用最大值右侧的子数组）。主函数constructMaximumBinaryTree初始化整个构建过程，传入整个数组和初始边界。

代码实现与注释

class Solution {
public:
    // 递归构建最大二叉树的辅助函数
    TreeNode* maxbinarytree(vector<int>& nums, int l, int r) {
        if (r - l == 0)  // 基本情况：子数组为空
            return nullptr;
            
        TreeNode* root = new TreeNode(0);  // 创建新节点
        int maxidx = l;  // 初始化最大值索引
        
        // 遍历当前子数组，找到最大值及其索引
        for (int i = l; i < r; i++) {
            root->val = max(root->val, nums[i]);
            if(root->val == nums[i])
                maxidx = i;
        }
        
        // 递归构建左子树和右子树
        root->left = maxbinarytree(nums, l, maxidx);
        root->right = maxbinarytree(nums, maxidx + 1, r);
        
        return root;  // 返回当前构建的子树
    }
    
    // 主函数：初始化最大二叉树构建过程
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return maxbinarytree(nums, 0, nums.size());
    }
};