LeetCode654.最大二叉树

ops/2024/11/17 1:18:59/

在这里插入图片描述

LeetCode刷题记录

文章目录

    • 📜题目描述
    • 💡解题思路
    • C++代码


📜题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

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

示例1

在这里插入图片描述

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。- 空数组,无子节点。- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。- 空数组,无子节点。- 只有一个元素,所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。- 只有一个元素,所以子节点是一个值为 0 的节点。- 空数组,无子节点。

示例2
在这里插入图片描述

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

💡解题思路

直接前序思想 –

  • 找到[left,right]的最大值 以及最大值坐标max_index,构造root

  • 然后划分左右子区间 [left,max_index-1] 和 [max_index+1,right]

  • 递归构造左右子区间: root -> left 和 root ->right

伪代码:TreeNode* ans([3,1,6,2,4,5])
{root = new TreeNode(6);root->left= ans([3,1]);root->right= ans([2,4,5]);return root;
}

上面是大致思路

具体需要考虑左右区间的划分,以及递归的结束条件。

C++代码

class Solution {
public:int findMaxIndex(vector<int>& nums,int left,int right){int max = INT_MIN;int max_index =left;//找最大while(left<=right){if(nums[left] > max){max = nums[left];max_index = left;}++left;}return max_index;}//借助辅助函数TreeNode* ans(vector<int>& nums,int left,int right){//递归的结束条件:left>rightif(left>right){return nullptr;}//找到最大值下标int max_index = findMaxIndex(nums,left,right);TreeNode* root = new TreeNode(nums[max_index]); //构造根//处理根的左和右//左区间:[left,max_index-1] //右区间:[max_index+1,right]root->left = ans(nums,left,max_index-1);root->right = ans(nums,max_index+1,right);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* root = ans(nums,0,nums.size()-1);return root;}
};

http://www.ppmy.cn/ops/134286.html

相关文章

Docker在微服务架构中的应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 Docker在微服务架构中的应用 Docker在微服务架构中的应用 Docker在微服务架构中的应用 引言 Docker 基本概念 1. 容器 2. 镜像 3…

动态IP代理技术详解与实现

目录 一、动态IP代理技术概述 二、动态IP代理技术的原理 代理服务器中转&#xff1a; IP地址动态更换&#xff1a; 协议支持&#xff1a; 智能调度机制&#xff1a; 三、动态IP代理的实现方法 基于HTTP代理的实现&#xff1a; 正向代理&#xff1a; 反向代理&#xf…

RestSharp基本使用方法

关于RestSharp RestSharp is a library that allows you to make REST and HTTP calls in .NET applications. It supports serialization, parameters, async functions, and more. RestSharp是C#的一个WepApi库&#xff0c;支持通用的Web接口处理&#xff0c;支持序列化、参数…

前端 JS 实用操作总结

目录 1、重构解构 1、数组解构 2、对象解构 3、...展开 2、箭头函数 1、简写 2、this指向 3、没有arguments 4、普通函数this的指向 3、数组实用方法 1、map和filter 2、find 3、reduce 1、重构解构 1、数组解构 const arr ["唐僧", "孙悟空&quo…

Odoo :一款免费开源的日化行业ERP管理系统

文 / 开源智造Odoo亚太金牌服务 概述 构建以 IPD 体系作为核心的产品创新研发管控体系&#xff0c;增进企业跨部门业务协同的效率&#xff0c;支撑研发管控、智慧供应链、智能制造以及全渠道营销等行业的场景化&#xff0c;构筑行业的研产供销财一体化管理平台。 行业的最新…

《深度学习》AlexNet网络

文章目录 1.AlexNet的网络架构2.示例&#xff1a;手写数字识别2.1 数据读取 学习目标&#xff1a; 知道AlexNet网络结构能够利用AlexNet完成图像分类 2012年&#xff0c;AlexNet横空出世&#xff0c;该模型的名字源于论⽂第⼀作者的姓名AlexKrizhevsky 。AlexNet使⽤了8层卷积…

Spring Boot编程训练系统:从概念到实现

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…

【2025最新计算机毕业设计】基于SpringBoot+Vue电脑在线装机指南教程网站【源码+文档】

作者简介&#xff1a;✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流。✌ 主要内容&#xff1a;&#x1f31f;Java项目、Python项目、前端项目、PHP、ASP.NET、人工智能…