LeetCode:1008. 前序遍历构造二叉搜索树
目录
题目描述:
代码:
第一种:
第二种:
第三种:分治法
题目描述:
给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。
保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。
二叉搜索树 是一棵二叉树,其中每个节点, Node.left
的任何后代的值 严格小于 Node.val
, Node.right
的任何后代的值 严格大于 Node.val
。
二叉树的 前序遍历 首先显示节点的值,然后遍历Node.left
,最后遍历Node.right
。
示例 1:
输入:preorder = [8,5,1,7,10,12] 输出:[8,5,10,1,7,null,12]
示例 2:
输入: preorder = [1,3] 输出: [1,null,3]
代码:
第一种:
从左到右依次建立二叉搜索树
public TreeNode bstFromPreorder1(int[] preorder) {TreeNode root=new TreeNode(preorder[0]);for(int i=1;i<preorder.length;i++){int val=preorder[i];insert1(root,val);}return root;}public TreeNode insert1(TreeNode root,int val){if(root==null){return new TreeNode(val);}if(val<root.val){root.left=insert1(root.left,val);}else{root.right=insert1(root.right,val);}return root;}
第二种:
上限法
public TreeNode bstFromPreorder2(int[] preorder) {return insert(preorder,Integer.MAX_VALUE);}int i=0;public TreeNode insert(int[] preorde,int max){//递归结束的条件if(preorde.length==0){return null;}int val=preorde[i];//如果超出上限,返回nullif(val>max){return null;}//创建节点TreeNode root=new TreeNode(val);i++;//没超过上限,设置其子孩子,设置完返回//preorder,5(自身值)root.left=insert(preorde,val);//preorder,8(上一个节点值)root.right=insert(preorde,max);return root;}
第三种:
//解法3:分治法 //8,5,1,7,10,12 /* * 根:8 * 左:5,1,7 * 右:10,12 * * 根:5 * 左:1 * 右:7 * * 根:10 * 左:null * 右:12 * */
public TreeNode bstFromPreorder(int[] preorder) {return partition(preorder,0,preorder.length-1);}private TreeNode partition(int[] preorder,int start,int end){if(start>end){return null;}TreeNode root=new TreeNode(preorder[start]);int index=start+1;while(index<=end){if(preorder[index]>preorder[start]){break;}index++;}//index 是右子树的起点root.left=partition(preorder,start+1,index-1);root.right=partition(preorder,index,end);return root;}
相关文章:

LeetCode:1008. 前序遍历构造二叉搜索树
目录 题目描述: 代码: 第一种: 第二种: 第三种:分治法 题目描述: 给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。 保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。 二叉搜索树 是一棵…...

gdb - 调试工具 - 入门 (一)
GDB(GNU Debugger)是GNU项目调试器的缩写,它是Linux下一个强大的C/C(以及其他语言如Fortran)程序调试工具。以下是对GDB的详细解释: 一、GDB的功能 GDB允许开发者对程序执行进行深入控制,可以…...
Swift内存访问冲突
内存的访问,发生在给变量赋值的时候,或者传递值(给函数)的时候,例如 var one 1//向one的内存区域发起一次写的操作 print("\(one)")//向one的内存区域发起一次读的操作 在 Swift 里,有很多修改…...

深入理解Spring(三)
目录 2.1.3、Spring配置非自定义Bean 1)配置Druid数据源交由Spring管理 2)配置Connection交由Spring管理 3)配置日期对象交由Spring管理 4)配置MyBatis的SqlSessionFactory交由Spring管理 2.1.4、Bean实例化的基本流程 1)Bean信息定义对象-BeanDefinition 2)DefaultLi…...

TB6612电机驱动模块使用指南
实物图: 简介:TB6612是一款双路H桥型直流电机驱动模块,可以控制两个直流电机的转速和方向 H桥:(双路H桥就是有两个这个结构) 引脚图:...

Paper -- 洪水深度估计 -- 利用图像处理和深度神经网络绘制街道照片中的洪水深度图
基本信息 论文题目:Flood depth mapping in street photos with image processing and deep neural networks 中文题目: 利用图像处理和深度神经网络绘制街道照片中的洪水深度图 作者及单位: Bahareh Alizadeh Kharazi,美国得克萨斯州立大…...
学习C#中的BackgroundWorker 组件
1. BackgroundWorker 组件概述 许多经常执行的操作可能需要很长的执行时间。 例如: 图像下载 Web 服务调用 文件下载和上载(包括点对点应用程序) 复杂的本地计算 数据库事务 本地磁盘访问(相对于内存访问来说其速度很慢&…...

【Vue3新工具】Pinia.js:提升开发效率,更轻量、更高效的状态管理方案!
大家好,欢迎来到程序视点!我是小二哥! 前言 在VUE项目开发中,一些数据常常被多个组件频繁使用,为了管理和维护这些数据,就出现了状态管理模式。 今天小二哥要给大家推荐的不是VueX,而是称为新…...

PCB 间接雷击模拟
雷击是一种危险的静电放电事件,其中两个带电区域会瞬间释放高达 1 千兆焦耳的能量。雷击就像一个短暂而巨大的电流脉冲,会对建筑物和电子设备造成严重损坏。雷击可分为直接和间接两类,其中间接影响是由于感应能量耦合到靠近雷击位置的物体。间…...

JAVA泛型和顺序表ArrayList
目录 泛型 泛型的定义: 泛型的实例化: 泛型的使用: 顺序表ArrayList 顺序表ArrayList的两种实例化方法: ArrayList常用的方法: 1. add 方法 2. size ( ) 方法 3. get 方法 4. set 方法 5. 顺序表的三种遍历元素的方法…...

Qt桌面应用开发 第六天(鼠标事件 定时器事件 定时器类 事件分发器 事件过滤器)
目录 1.1鼠标进入和离开enterEvent\leaveEvent 1.2鼠标按下释放和移动mousePressEvent\mouseReleaseEvent\mouseMoveEvent 1.3定时器事件timerEvent 1.4定时器类QTimer 1.5事件分发器event 1.6事件过滤器eventFilter 1.1鼠标进入和离开enterEvent\leaveEvent 事件&#x…...
Javascript高级—深入JS模板字符串的高级用法
深入JS模板字符串的高级用法:解锁动态内容生成的无限可能 在JavaScript编程中,模板字符串(Template Literals)自ES6(ECMAScript 2015)引入以来,就以其简洁、直观的特性迅速成为开发者们生成动态…...
14. 【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--章节总结
本章重点介绍了如何在一个简单的系统中实现基本的权限管理功能。通过构建一个简单的权限控制模型,章节阐述了如何为用户分配权限,并在应用程序中进行访问控制。 一、关键要点: 1. 用户管理(登录/注册/Token) 本章节聚…...

vulhub之fastjson
fastjson 1.2.24 反序列化 RCE 漏洞(CVE-2017-18349) 漏洞简介 什么是json json全称是JavaScript object notation。即JavaScript对象标记法,使用键值对进行信息的存储。举个简单的例子如下: {"name":"BossFrank", "age":23, "isDevel…...

2024年亚太地区数学建模大赛D题-探索量子加速人工智能的前沿领域
量子计算在解决复杂问题和处理大规模数据集方面具有巨大的潜力,远远超过了经典计算机的能力。当与人工智能(AI)集成时,量子计算可以带来革命性的突破。它的并行处理能力能够在更短的时间内解决更复杂的问题,这对优化和…...

卷积神经网络各层介绍
目录 1 卷积层 2 BN层 3 激活层 3.1 ReLU(Rectified Linear Unit) 3.2 sigmoid 3.3 tanh(双曲正切) 3.4 Softmax 4 池化层 5 全连接层 6 模型例子 1 卷积层 卷积是使用一个卷积核(滤波器)对矩阵进…...

Python应用指南:高德拥堵延时指数
随着城市化进程的加快,交通拥堵问题日益严重,成为影响城市居民生活质量的重要因素之一。为了科学评估和管理交通拥堵,各种交通拥堵指数应运而生。其中,高德地图提供的“拥堵延时指数”因其数据丰富、实时性强和应用广泛而备受关注…...
ISO 21434标准:汽车网络安全管理的利与弊
ISO 21434标准在提升汽车网络安全性方面起到了重要作用,但任何标准都不是完美无缺的,ISO 21434标准也存在一些不足之处。以下是对其不足之处的分析: 一、标准的灵活性与适应性 缺乏具体技术细节:ISO 21434标准更多地提供了网络安…...

无插件H5播放器EasyPlayer.js视频流媒体播放器如何开启electron硬解码Hevc(H265)
在数字化时代,流媒体播放器技术正经历着前所未有的变革。随着人工智能、大数据、云计算等技术的融合,流媒体播放器的核心技术不断演进,为用户提供了更加丰富和个性化的观看体验。 EasyPlayer.js H5播放器,是一款能够同时支持HTTP、…...

excel版数独游戏(已完成)
前段时间一个朋友帮那小孩解数独游戏,让我帮解,我看他用电子表格做,只能显示,不能显示重复,也没有协助解题功能,于是我说帮你做个电子表格版的“解题助手”吧,不能直接解题,但该有的…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...

Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...