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

胡志明t

题目重解

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

解题思路解析

典型分治策略：

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

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

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

代码和注释

1. class Solution {
   
2. public:
   
3.     TreeNode* maxbinarytree(vector<int>& nums, int l, int r) {
   
4.         if (r - l == 0)  // 子数组为空时返回nullptr
   
5.             return nullptr;
   
6.             
   
7.         TreeNode* root = new TreeNode(0);  // 创建当前根节点
   
8.         int maxidx = l;  // 初始化**值索引
   
9.         
   
10.         // 遍历当前子数组寻找**值
    
11.         for (int i = l; i < r; i++) {
    
12.             root->val = max(root->val, nums[i]);  // 更新**值
    
13.             if(root->val==nums[i])
    
14.                 maxidx=i;  // 记录**值位置
    
15.         }
    
16.         
    
17.         // 递归构建左右子树
    
18.         root->left = maxbinarytree(nums, l, maxidx);  // 左子数组构建左子树
    
19.         root->right = maxbinarytree(nums, maxidx + 1, r);  // 右子数组构建右子树
    
20.         
    
21.         return root;  // 返回当前构造的子树
    
22.     }
    
23.    
    
24.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    
25.         return maxbinarytree(nums, 0, nums.size());  // 从完整数组开始构建
    
26.     }
    
27. };

复制代码

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