当前位置: 首页 > news >正文

12.04 二叉树中等题

513. 找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

思路:找到最低层中最左侧的节点值,比较适合层序遍历,返回最低层的第一个值即可。

细节:判断是否是最低层,需要保存节点的当前层数。可以用queue<pair>来保存pair保存<节点指针,层数>

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {if(!root) return -1;queue<pair<TreeNode*,int>> q;q.push({root,1});int deepthMax=1;int ret=root->val;while(!q.empty()){pair<TreeNode*,int> pariFront=q.front();TreeNode* nodeFront=pariFront.first;int deepth=pariFront.second;//判断是否是更低的一层if(deepth>deepthMax){deepthMax=deepth;ret=nodeFront->val;}q.pop();if(nodeFront->left) q.push({nodeFront->left,deepth+1});if(nodeFront->right) q.push({nodeFront->right,deepth+1});}return ret;}
};
  • 时间复杂度:O(n),其中 nnn 是二叉树的节点数目。



654. 最大二叉树

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

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

返回 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 的节点。- 空数组,无子节点。

 思路:最简单的方法是直接按照题目描述进行模拟。

左子树为 construct(nums,left,best−1)

右子树为 construct(nums,best+1,right)

当递归到一个空数组时,便可以返回一棵空的树。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findMaxIndex(vector<int>& nums){int ret=0;for(int i=1;i<nums.size();i++){if(nums[i]>nums[ret]) ret=i;}return ret;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.empty()) return nullptr;int maxIndex=findMaxIndex(nums);vector<int> leftNums(nums.begin(),nums.begin()+maxIndex);vector<int> rightNums(nums.begin()+maxIndex+1,nums.end());TreeNode* root=new TreeNode(nums[maxIndex],constructMaximumBinaryTree(leftNums), //左子树constructMaximumBinaryTree(rightNums)); //右子树return root;}
};

时间复杂度:O(n^2),其中 nnn 是数组 nums\textit{nums}nums 的长度。在最坏的情况下,数组严格递增或递减,需要递归 n 层,第 i (0≤i<n)层需要遍历 n−i个元素以找出最大值,总时间复杂度为 O(n2)

思路2:利用单调栈可以实现时间复杂度O(n)

代码随想录

相关文章:

12.04 二叉树中等题

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路&#xff1a;找到最低层中最左侧的节点值&#xff0c;比较适合层序遍历&#xff0c;返回最…...

Redis的安装

本文采用原生的方式安装Redis&#xff0c;Redis的版本为5.0.5 安装 下载 下载网站&#xff1a;https://download.redis.io/releases/ wget http://download.redis.io/releases/redis-5.0.5.tar.gz解压 tar -zxvf redis-5.0.5.tar.gz进入redis目录 cd redis-5.0.5执行编译…...

JDK安装太麻烦?一篇文章搞定

JDK是 Java 语言的软件开发工具包&#xff0c;主要用于移动设备、嵌入式设备上的java应用程序。JDK是整个java开发的核心&#xff0c;它包含了JAVA的运行环境&#xff08;JVMJava系统类库&#xff09;和JAVA工具。 JDK包含的基本组件包括&#xff1a; javac – 编译器&#xf…...

漫谈HBuilderX App-Jenkins热更新构建

漫谈Uniapp App热更新包-Jenkins CI/CD打包工具链的搭建 零、写在前面 HBuilderX是DCloud旗下的IDE产品&#xff0c;目前只提供了Windows和Mac版本使用。本项目组在开发阶段经常需要向测试环境提交热更新包&#xff0c;使用Jenkins进行CD是非常有必要的一步。尽管HBuilderX提…...

技术前沿丨Teranode如何实现无限扩容

​​发表时间&#xff1a;2023年9月15日 BSV区块链协会的技术团队目前正在努力开发Teranode&#xff0c;这是一款比特币节点软件&#xff0c;其最终目标是实现比特币的无限扩容。然而&#xff0c;正如BSV区块链协会网络基础设施负责人Jake Jones在2023年6月举行的伦敦区块链大会…...

世岩清上:如何制作年终工作汇报宣传片

年终工作汇报宣传片是一种以视觉和口头语言为主要表现形式的宣传手段&#xff0c;旨在向领导、同事、客户等展示一年来的工作成果和亮点。以下是制作年终工作汇报宣传片的几个关键步骤&#xff1a; 明确目的和受众&#xff1a;在制作宣传片前&#xff0c;要明确宣传片的目的和受…...

练习十一:简单卷积器的设计

简单卷积器的设计 1&#xff0c;任务目的&#xff1a;2&#xff0c;明确设计任务2.1,目前这部分代码两个文件没找到&#xff0c;见第5、6节&#xff0c;待解决中。 &#xff0c;卷积器的设计&#xff0c;RTL&#xff1a;con1.v4&#xff0c;前仿真和后仿真&#xff0c;测试信号…...

外包干了4年,技术退步太明显了。。。。。

先说一下自己的情况&#xff0c;本科生生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年国庆&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测…...

微服务实战系列之EhCache

前言 书接前文&#xff0c;继续深耕。上一篇博主对Redis进行了入门级介绍&#xff0c;大体知道了Redis可以干什么以及怎么使用它。 今日博主继续带着大家学习如何使用EhCache&#xff0c;这是一款基于Java的缓存框架。 微服务实战系列之Redis微服务实战系列之Cache微服务实战…...

SpringBoot:SpringMVC(上)

文章目录 前言一、SpringMVC是什么&#xff1f;1.1 MVC的定义&#xff1a;1.2 MVC 和 Spring MVC 的关系 二、Spring MVC 创建和连接2.1创建springmvc2.2接下来&#xff0c;创建⼀个 UserController 类&#xff0c;实现⽤户到 Spring 程序的互联互通&#xff0c;具体实现代码如…...

一文搞懂Go语言中包导入

一文搞懂Go语言中包导入 定义包 在go语言中&#xff0c;定义包的关键字为package&#xff0c;如package main等&#xff0c;在go语言中有一个约定俗成的标准&#xff0c;那就是包名与目录名把持一致。 //service目录下 package servicepackage utils 可以看到&#xff0c;我…...

Vue2学习笔记(事件处理)

一、基本使用 1.使用v-on:xxx 或 xxx 绑定事件&#xff0c;其中xxx是事件名&#xff1b;2.事件的回调需要配置在methods对象中&#xff0c;最终会在vm上&#xff1b;3.methods中配置的函数&#xff0c;不要用箭头函数&#xff01;否则this就不是vm了&#xff1b;4.methods中配…...

【2023第十二届“认证杯”数学中国数学建模国际赛】A题 太阳黑子预报完整解题思路

A题 太阳黑子预报 题目任务思路分析第一问第二问第三问 题目 太阳黑子是太阳光球上的一种现象&#xff0c;表现为比周围区域更暗的临时斑点。它们是由于磁通量集中而导致表面温度降低的区域&#xff0c;磁通量的集中抑制了对流。太阳黑子出现在活跃区域内&#xff0c;通常成对…...

Huawei FusionSphere FusionCompte FusionManager

什么是FusionSphere FusionSphere 解决方案不独立发布软件&#xff0c;由各配套部件发布&#xff0c;请参 《FusionSphere_V100R005C10U1_版本配套表_01》。 目前我们主要讨论FusionManager和FusionCompute两个组件。 什么是FusionCompte FusionCompute是华为提供的虚拟化软…...

GSLB是什么?谈谈对该技术的一点理解

GSLB是什么&#xff1f;它又称为全局负载均衡&#xff0c;是主流的负载均衡类型之一。众所周知&#xff0c;负载均衡位于服务器的前面&#xff0c;负责将客户端请求路由到所有能够满足这些请求的服务器&#xff0c;同时最大限度地提高速度和资源利用率&#xff0c;并确保无任何…...

【接口测试】POST请求提交数据的三种方式及Postman实现

1. 什么是POST请求&#xff1f; POST请求是HTPP协议中一种常用的请求方法&#xff0c;它的使用场景是向客户端向服务器提交数据&#xff0c;比如登录、注册、添加等场景。另一种常用的请求方法是GET&#xff0c;它的使用场景是向服务器获取数据。 2. POST请求提交数据的常见编…...

SpringBoot系列之集成Jedis教程

SpringBoot系列之集成Jedis教程&#xff0c;Jedis是老牌的redis客户端框架&#xff0c;提供了比较齐全的redis使用命令&#xff0c;是一款开源的Java 客户端框架&#xff0c;本文使用Jedis3.1.0加上Springboot2.0&#xff0c;配合spring-boot-starter-data-redis使用&#xff0…...

centos用什么命令可查看版本号

概述 查版本号的命令&#xff1a;1、“cat /etc/redhat-release”&#xff0c;可输出centos版本号&#xff1b;2、“cat /proc/version”、“uname -a”或“uname -r”&#xff0c;可输出内核版本号。 本教程操作环境&#xff1a;centos7.9.2009系统。 查看centos版本 [roo…...

大数据之Redis

NoSQL SQL数据库泛指关系型数据库NoSQL不拘泥于关系型数据的设计范式&#xff0c;放弃了通用的技术标准&#xff0c;为某一特定领域场景而设计 NoSQL的特点 不遵循SQL标准不支持ACID远超SQL的性能 NoSQL的适用场景 对数据高并发的读写海量数据的读写对数据高可扩展性的 N…...

【React设计】React企业级设计模式

Image Source : https://bugfender.com React是一个强大的JavaScript库&#xff0c;用于构建用户界面。其基于组件的体系结构和构建可重用组件的能力使其成为许多企业级应用程序的首选。然而&#xff0c;随着应用程序的规模和复杂性的增长&#xff0c;维护和扩展变得更加困难。…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...

Linux基础开发工具——vim工具

文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...