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

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...