找回密码
 立即注册
查看: 17|回复: 0

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

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:15
  • 打卡月天数:1
  • 打卡总奖励:117
  • 最近打卡:2025-08-02 15:29:27

21

主题

5

回帖

2388

积分

VIP

积分
2388
发表于 2025-7-22 11:24:45 | 显示全部楼层 |阅读模式
15.jpg
题目重解
我们面对一个看似简单却充满递归魅力的题目:给定一个不含重复元素的整数数组,需要构建一棵特殊的二叉树。这个的每个父节点都必须是当前子数组中的**元素,而它的左右子树则分别由该**值左侧和右侧的子数组以相同规则构建。这就像是在数组中不断寻找"**者",然后让这个**者统领它的左右领地。
解题思路解析
典型分治策略
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. TreeNode* root = new TreeNode(0); // 创建当前根节点
  7. int maxidx = l; // 初始化**值索引

  8. // 遍历当前子数组寻找**值
  9. for (int i = l; i < r; i++) {
  10. root->val = max(root->val, nums[i]); // 更新**值
  11. if(root->val==nums[i])
  12. maxidx=i; // 记录**值位置
  13. }

  14. // 递归构建左右子树
  15. root->left = maxbinarytree(nums, l, maxidx); // 左子数组构建左子树
  16. root->right = maxbinarytree(nums, maxidx + 1, r); // 右子数组构建右子树

  17. return root; // 返回当前构造的子树
  18. }

  19. TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
  20. return maxbinarytree(nums, 0, nums.size()); // 从完整数组开始构建
  21. }
  22. };
复制代码

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表