代码随想录二刷 | 二叉树 | 最大二叉树

代码随想录二刷 | 二叉树 | 最大二叉树

  • 题目描述
  • 解题思路
  • 代码实现

题目描述

654.最大二叉树

给定一个不重复的整数数组 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 中的所有整数 互不相同

解题思路

构造树一般采用的是前序遍历,先构建中间节点,再构建左子树和右子树。

  • 确定递归函数的参数和返回值
    参数传入的是存放元素的数组,返回该数组构建的二叉树,因此返回值为指向节点的指针
    TreeNode* constructMaximumBinaryTree(vector<int>& nums)
    
  • 确定终止条件
    题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况。
    那么当递归遍历的时候如果传入的数组大小为1,说明遍历到了叶子节点了。
    所以此时应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。
    这表示一个数组大小是1的时候,构造了一个新的节点,并返回。
    TreeNode* node = new TreeNode(0);
    if (nums.size() == 1) {node->val = nums[0];return node;
    }
    
  • 确定单层递归的逻辑
    先找到数组中最大的值和对应的下标,最大的值构造根节点,下标用来分隔数组。
    int maxValue = 0; // 用于构造根节点
    int maxValueIndex = 0;// 用于分隔数组
    for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxValueIndex = i;}
    }
    TreeNode* node = new TreeNode(0);
    node->val = maxValue;
    
    最大值所在的下标左区间,构造左子树
    要保证左区间至少有一个数值,所以需要maxValue > 0
    if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.end() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);
    }
    
    最大值所在的下标右区间,构造右子树
    要保证右子树至少有一个数值,所以maxValueIndex < (nums.size() - 1)
    if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);
    }
    

代码实现

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* node = new TreeNode(0);if (nums.size() == 1) {node->val = nums[0];return node;}// 寻找数组中最大的值和对应的下标int maxValue = 0;int maxValueIndex = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxValueIndex = i;}}node->val = maxValue;// 最大值所在左区间if (maxValueIndex > 0) {vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);node->left = constructMaximumBinaryTree(newVec);}// 最大值所在右区间if (maxValueIndex < (nums.size() - 1)) {vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());node->right = constructMaximumBinaryTree(newVec);}return node;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659830.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

SpringSecurity6 | 默认用户生成(上)

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏: MySQL学习 🥭本文内容:SpringSecurity6 | 默认用户生成(上) 📚个人知识库: [Leo知识库]https://gaozim…

基于STM8S103F3P6的超声波测距仪设计

大三的时候给大四学长做的毕业设计题目 文章目录 1 绪论1.1 设计背景1.2 设计的主要任务 2 超声波测距基本理论及总体架构2.1 基本知识2.1.1 超声波特性2.1.2 超声波传感器2.1.3 超声波测距原理 2.2 总体架构2.2.1 设计原则2.2.2 总体方案介绍 2.3 主要器件选择与介绍2.3.1 主控…

网盘项目话术(0.5w字精选)

功能结构图 数据库设计总结 该项目主要就是对文件的操作&#xff0c;file表&#xff0c;file_share表。 file表主要字段&#xff1a;id&#xff0c;用户id&#xff0c;父级目录id&#xff0c;文件的地址&#xff0c;文件的封面图片地址&#xff0c;创建和修改时间。 file_sha…

react 之 美团案例

1.案例展示 2.环境搭建 克隆项目到本地&#xff08;内置了基础静态组件和模版&#xff09; git clone http://git.itcast.cn/heimaqianduan/redux-meituan.git 安装所有依赖 npm i 启动mock服务&#xff08;内置了json-server&#xff09; npm run serve 启动前端服务 npm…

Translation翻译插件

Translation插件是为IntelliJ IDEA开发的&#xff0c;因此只能在IntelliJ IDEA中使用。但是&#xff0c;如果你需要在其他软件中进行翻译&#xff0c;可以考虑使用其他的翻译工具或服务。例如&#xff0c;一些在线翻译网站&#xff08;如Google翻译、百度翻译等&#xff09;提供…

VScode——下载、安装、配置C/C++环境(windows)

一.快速下载 还在因为vscode官方下载慢而头疼嘛&#xff0c;按这个步骤来直接起飞兄弟萌 首先进入vscode官方网站然后选择对应版本下载然后进入浏览器下载页面复制下载链接粘贴到地址栏 将地址中的/stable前换成vscode.cdn.azure.cn 即可实现超速下载 下面是一个国内镜像的下…

mysql原理--MySQL基于规则的优化

设计 MySQL 的大叔依据一些规则&#xff0c;竭尽全力的把一些很糟糕的语句转换成某种可以比较高效执行的形式&#xff0c;这个过程也可以被称作 查询重写 &#xff08;就是人家觉得你写的语句不好&#xff0c;自己再重写一遍&#xff09;。 1.条件化简 我们编写的查询语句的搜…

vue虚拟列表展示

效果图 <template><!-- 总体高度区域 --><divref"listWrap"class"m-container"scroll"scrollListener"><div:style"handleContainerHeight()"><!-- 可视区域 --><divclass"m-area":style&…

打地鼠游戏来了

主要利用js鼠标点击事件和window.setInterval&#xff08;&#xff09;回调函数来进行实现的. 源码获取方式&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1eW9qvX3zFH9qlH82-I4yOA 提取码&#xff1a;1233

中间件系列 - Redis入门到实战(原理篇)

前言 学习视频&#xff1a; 黑马程序员Redis入门到实战教程&#xff0c;深度透析redis底层原理redis分布式锁企业解决方案黑马点评实战项目 中间件系列 - Redis入门到实战 本内容仅用于个人学习笔记&#xff0c;如有侵扰&#xff0c;联系删除 学习目标 Redis数据结构Redis网…

Matlab:非线性规划

1、语法&#xff1a; xfmincon(fun,x0,A,b) xfmincon(fun,x0,A,b,Aeq,beq) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) xfmincon(problem) [x,fval]fmincon(___) [x,fval,exitflag,…

搭建FTP服务器详细介绍

一.FTP简介 &#xff11;.&#xff11;什么是FTP &#xff11;.&#xff12;FTP服务器介绍 &#xff11;.&#xff13;FTP服务器优缺点 二.FTP服务器的搭建与配置 2.1 开启防火墙 2.2创建组 2.3创建用户 2.4安装FTP服务器 2.5配置FTP服务器 &#xff12;.&#xff…

日常中msvcp120.dll丢失五种解决方法

在日常使用电脑的过程中&#xff0c;我们可能会遇到一些错误提示&#xff0c;其中之一就是“msvcp120.dll丢失”。那么&#xff0c;msvcp120.dll到底是什么&#xff1f;它的作用又是什么呢&#xff1f;为什么会出现丢失的情况呢&#xff1f;本文将为您详细介绍msvcp120.dll的相…

无法连接虚拟机设备 ide1:0,因为主机上没有相应的设备。您要每次在开启此虚拟机时都尝试连接此虚拟设备吗?

Vmware报错&#xff1a; 报错原因&#xff1a; ide1:0一般是虚拟机的光驱&#xff0c;配置选项是“使用物理驱动器”&#xff0c;而宿主机可能没有安装光驱&#xff0c;故无法从驱动器上寻找 .ISO 系统文件。 解决方法: 右键点击对应的虚拟机&#xff0c;再点击“设置”按钮。…

百度每天20%新增代码由AI生成,Comate SaaS服务8000家客户 采纳率超40%

12月28日&#xff0c;由深度学习技术及应用国家工程研究中心主办的WAVE SUMMIT深度学习开发者大会2023在北京召开。百度首席技术官、深度学习技术及应用国家工程研究中心主任王海峰现场公布了飞桨文心五载十届最新生态成果&#xff0c;文心一言最新用户规模破1亿&#xff0c;截…

轻量应用服务器与云服务器CVM对比——腾讯云

腾讯云轻量服务器和云服务器CVM该怎么选&#xff1f;不差钱选云服务器CVM&#xff0c;追求性价比选择轻量应用服务器&#xff0c;轻量真优惠呀&#xff0c;活动 https://curl.qcloud.com/oRMoSucP 轻量应用服务器2核2G3M价格62元一年、2核2G4M价格118元一年&#xff0c;540元三…

❀My学习小记录之算法❀

目录 算法:) 一、定义 二、特征 三、基本要素 常用设计模式 常用实现方法 四、形式化算法 五、复杂度 时间复杂度 空间复杂度 六、非确定性多项式时间&#xff08;NP&#xff09; 七、实现 八、示例 求最大值算法 求最大公约数算法 九、分类 算法:) 一、定义 …

dvwa问题篇 -- dvwa出现数据库无法访问的时候,Could not connect to the MySQL service. -- 小黑解决教程

各位小伙伴初次玩dvwa会出现各种问题&#xff0c;本来想把一些问题直接总结写一篇dvwa文章来着&#xff0c;但因为都是关键字搜索&#xff0c;所以将一些问题都拆分出来&#xff0c;以便大家方便查类似问题。&#xff08;大家有遇到不一样的问题欢迎投稿&#xff01;&#xff0…

VSCode 如何安装插件的历史版本

背景 在日常开发过程中&#xff0c;我们可能会遇到新版VSCode插件存在问题&#xff0c;无法正常工作的情况。这种情况下&#xff0c;一种可行的解决方案就是安装插件的历史版本。VSCode 插件默认安装的都是插件最新的版本&#xff0c;例如下面 vscode-styled-compoents 插件 本…

web自动化之常见的异常,selenium.common.exceptions.StaleElementReferenceException

1.问题描述 selenium自动化代码&#xff0c;报错selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: element is not attached to the page document StaleElementReferenceException是陈旧的元素引用异常 这个异常发生在 获…