力扣654：递归分治的艺术 如何用最大元素构建二叉树

题目重解

我们面对一个看似简单却充满递归魅力的题目：给定一个不含重复元素的整数数组，需要构建一棵特殊的二叉树。这个树的每个父节点都必须是当前子数组中的最大元素，而它的左右子树则分别由该最大值左侧和右侧的子数组以相同规则构建。这就像是在数组中不断寻找"王者"，然后让这个王者统领它的左右领地。

解题思路解析

典型分治策略：

1.基准情况：当子数组范围为空时（l == r），返回空指针

2.寻找最大值：在当前子数组范围内遍历，记录最大值及其索引

3.递归构建：以最大值为界，左侧子数组构建左子树，右侧子数组构建右子树 整个过程就像是在不断分割数组的疆域，每个最大值节点都成为该区域的统治者，其左右边界自然划分出它的势力范围。递归的终止条件确保了当领地缩小到空集时停止扩张。

代码和注释

class Solution {
public:
    TreeNode* maxbinarytree(vector<int>& nums, int l, int r) {
        if (r - l == 0)  // 子数组为空时返回nullptr
            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());  // 从完整数组开始构建
    }
};