LeetCode654.最大二叉树

在这里插入图片描述

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.rhkb.cn/news/472091.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

电子应用产品设计方案-9:全自动智能马桶系统设计方案

一、系统概述 本全自动智能马桶系统旨在提供舒适、卫生、便捷和智能化的如厕体验。通过融合多种传感器技术、电子控制单元和机械执行机构&#xff0c;实现马桶的自动冲洗、座圈加热、臀部清洗、烘干等功能&#xff0c;并具备智能感应、用户个性化设置和健康监测等特色功能。 二…

酒水分销积分商城小程序开发方案php+uniapp

酒水分销积分商城小程序开发&#xff0c;开发语言后端php&#xff0c;前端uniapp。核心功能模块&#xff1a;酒水商城、积分商城、二级分销、抽奖、优惠券。可以二开或定制。协助部署搭建。

UNIX网络编程-TCP套接字编程(实战)

概述 TCP客户端/服务器程序示例是执行如下步骤的一个回射服务器&#xff1a; 客户端从标准输入读入一行文本&#xff0c;并写给服务器。服务器从网络输入读入这行文本&#xff0c;并回射给客户端。客户端从网络输入读入这行回射文本&#xff0c;并显示在标准输出上。 TCP服务器…

Kafka-Eagle的配置——kafka可视化界面

通过百度网盘分享的文件&#xff1a;kafka-eagle-bin-2.0.8.tar.gz 链接&#xff1a;https://pan.baidu.com/s/1H3YONkL97uXbLTPMZHrfdg?pwdsltu 提取码&#xff1a;sltu 一、界面展示 二、软件配置 1、关闭kafka集群 kf.sh stop 2、将该软件上传到/opt/modules下 cd /opt…

Uniapp踩坑input自动获取焦点ref动态获取实例不可用

前言 大家好我是没钱的君子下流坯&#xff0c;用自己的话解释自己的知识。很久很更新了&#xff0c;这几个月一直在加班&#xff0c;今天记录一个uniapp关于input中focus()方法自动获取焦点的坑。 案例 为了实现一个手机验证码的页面&#xff0c;验证码是五个输入框&#xf…

报错 No available slot found for the embedding model

报错内容 Server error: 503 - [address0.0.0.0:12781, pid304366] No available slot found for the embedding model. We recommend to launch the embedding model first, and then launch the LLM models. 目前GPU占用情况如下 解决办法: 关闭大模型, 先把 embedding mode…

AI大模型(二):AI编程实践

一、软件安装 1. 安装 Visual Studio Code VSCode官方下载&#xff1a;Visual Studio Code - Code Editing. Redefined 根据自己的电脑系统选择相应的版本下载 安装完成&#xff01; 2. 安装Tongyi Lingma 打开VSCode&#xff0c;点击左侧菜单栏【extensions】&#xff0c;…

MFC程序崩溃时生成dmp文件

#include “HiExceptionHandle.h” #include <string> #pragma once class HiExceptionHandle { public:HiExceptionHandle(void);~HiExceptionHandle(void); public:void RunCrashHandler();void SetWERDumpLocation(const std::wstring dumpFolderPath); protected:st…

释放高级功能:Nexusflows Athene-V2-Agent在工具使用和代理用例方面超越 GPT-4o

在不断发展的人工智能领域&#xff0c;Nexusflows 推出了 Athene-V2-Agent 作为其模型系列的强大补充。这种专门的代理模型设计用于在功能调用和代理应用中发挥出色作用&#xff0c;突破了人工智能所能达到的极限。 竞争优势 Athene-V2-Agent 不仅仅是另一种人工智能模型&…

Flutter:input输入框

输入框&#xff1a; // 是否显示关闭按钮 bool _showClear false; // 文字编辑控制器&#xff0c;监听搜索框的变化。 final TextEditingController _controller TextEditingController(); // 输入框发生变化事件 void _onChange(String value){if(value.length > 0){setS…

vue 项目使用 nginx 部署

前言 记录下使用element-admin-template 改造项目踩过的坑及打包部署过程 一、根据权限增加动态路由不生效 原因是Sidebar中路由取的 this.$router.options.routes,需要在计算路由 permission.js 增加如下代码 // generate accessible routes map based on roles const acce…

鸿蒙next ui安全区域适配(刘海屏、摄像头挖空等)

目录 相关api 团结引擎对于鸿蒙的适配已经做了安全区域的适配&#xff0c;也考虑到了刘海屏和摄像机挖孔的情况&#xff0c;在团结引擎内可以直接使用Screen.safeArea 相关api 团结引擎对于鸿蒙的适配已经做了安全区域的适配&#xff0c;也考虑到了刘海屏和摄像机挖孔的情况&am…

多端校园圈子论坛小程序,多个学校同时代理,校园小程序分展示后台管理源码

社团活动与组织 信息发布&#xff1a;系统支持社团发布活动信息、招募新成员等&#xff0c;方便社团进行线上线下活动的组织和管理。 增强凝聚力&#xff1a;通过系统&#xff0c;社团成员可以更好地交流和互动&#xff0c;增强社团的凝聚力和影响力。 生活服务功能 二手市场…

SpringCloud-使用FFmpeg对视频压缩处理

在现代的视频处理系统中&#xff0c;压缩视频以减小存储空间、加快传输速度是一项非常重要的任务。FFmpeg作为一个强大的开源工具&#xff0c;广泛应用于音视频的处理&#xff0c;包括视频的压缩和格式转换等。本文将通过Java代码示例&#xff0c;向您展示如何使用FFmpeg进行视…

MySQL-初识数据库

目录 一、数据库基础概念 1、SQL 2、数据&#xff08;Data&#xff09; 3、数据库&#xff08;DB&#xff09; 4、数据库管理系统DBMS 5、数据库系统DBS 6、关系模型&#xff08;Relational Model&#xff09; 7、E-R图 8、常见的数据库 9、数据库基本操作 一、数据库…

【C语言】实现二维数组按列排序

文章目录 代码实现代码解释注意事项 代码实现 下面是一个C语言程序&#xff0c;它读取用户输入的4行5列的二维数组&#xff0c;并按照列对数组进行排序。 #include <stdio.h>int main() {int a[4][5]; // 定义一个4行5列的二维数组// 读取用户输入的二维数组for (int i…

aws ses 设置发件人昵称

看到别人的发的都是有昵称的&#xff0c;自己发的就是直接展示noreply 其实很简单&#xff1a; 只需要把发件人改成“nickname<noreplyxxx.com>”就行了

51c大模型~合集42

我自己的原文哦~ https://blog.51cto.com/whaosoft/11859244 #猎户座 「草莓」即将上线&#xff0c;OpenAI新旗舰大模型曝光&#xff0c;代号「猎户座」 ChatGPT 要进化了&#xff1f; 本月初&#xff0c;OpenAI 创始人、CEO 山姆・奥特曼突然在 X 上发了一张照片&#xff0…

【算法】二分查找

基本内容 提高在有序的数组中查找满足某一条件的索引 二分查找的基本类型 ① 有多种情况满足条件&#xff0c;找到满足条件的最右索引&#xff0c;例如找到值为4的最右索引&#xff08;也可以换为小于5的最后一个元素&#xff09; ​ ② 有多种情况满足条件&#xff0c;找到满…

PCA 原理推导

针对高维数据的降维问题&#xff0c;PCA 的基本思路如下&#xff1a;首先将需要降维的数据的各个变量标准化&#xff08;规范化&#xff09;为均值为 0&#xff0c;方差为 1 的数据集&#xff0c;然后对标准化后的数据进行正交变换&#xff0c;将原来的数据转换为若干个线性无关…