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

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. 前序遍历构造二叉搜索树

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

gdb - 调试工具 - 入门 (一)

GDB&#xff08;GNU Debugger&#xff09;是GNU项目调试器的缩写&#xff0c;它是Linux下一个强大的C/C&#xff08;以及其他语言如Fortran&#xff09;程序调试工具。以下是对GDB的详细解释&#xff1a; 一、GDB的功能 GDB允许开发者对程序执行进行深入控制&#xff0c;可以…...

Swift内存访问冲突

内存的访问&#xff0c;发生在给变量赋值的时候&#xff0c;或者传递值&#xff08;给函数&#xff09;的时候&#xff0c;例如 var one 1//向one的内存区域发起一次写的操作 print("\(one)")//向one的内存区域发起一次读的操作 在 Swift 里&#xff0c;有很多修改…...

深入理解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电机驱动模块使用指南

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

Paper -- 洪水深度估计 -- 利用图像处理和深度神经网络绘制街道照片中的洪水深度图

基本信息 论文题目&#xff1a;Flood depth mapping in street photos with image processing and deep neural networks 中文题目: 利用图像处理和深度神经网络绘制街道照片中的洪水深度图 作者及单位&#xff1a; Bahareh Alizadeh Kharazi&#xff0c;美国得克萨斯州立大…...

学习C#中的BackgroundWorker 组件

1. BackgroundWorker 组件概述 许多经常执行的操作可能需要很长的执行时间。 例如&#xff1a; 图像下载 Web 服务调用 文件下载和上载&#xff08;包括点对点应用程序&#xff09; 复杂的本地计算 数据库事务 本地磁盘访问&#xff08;相对于内存访问来说其速度很慢&…...

【Vue3新工具】Pinia.js:提升开发效率,更轻量、更高效的状态管理方案!

大家好&#xff0c;欢迎来到程序视点&#xff01;我是小二哥&#xff01; 前言 在VUE项目开发中&#xff0c;一些数据常常被多个组件频繁使用&#xff0c;为了管理和维护这些数据&#xff0c;就出现了状态管理模式。 今天小二哥要给大家推荐的不是VueX&#xff0c;而是称为新…...

PCB 间接雷击模拟

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

JAVA泛型和顺序表ArrayList

目录 泛型 泛型的定义&#xff1a; 泛型的实例化&#xff1a; 泛型的使用&#xff1a; 顺序表ArrayList 顺序表ArrayList的两种实例化方法&#xff1a; ArrayList常用的方法&#xff1a; 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模板字符串的高级用法&#xff1a;解锁动态内容生成的无限可能 在JavaScript编程中&#xff0c;模板字符串&#xff08;Template Literals&#xff09;自ES6&#xff08;ECMAScript 2015&#xff09;引入以来&#xff0c;就以其简洁、直观的特性迅速成为开发者们生成动态…...

14. 【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--章节总结

本章重点介绍了如何在一个简单的系统中实现基本的权限管理功能。通过构建一个简单的权限控制模型&#xff0c;章节阐述了如何为用户分配权限&#xff0c;并在应用程序中进行访问控制。 一、关键要点&#xff1a; 1. 用户管理&#xff08;登录/注册/Token&#xff09; 本章节聚…...

vulhub之fastjson

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

2024年亚太地区数学建模大赛D题-探索量子加速人工智能的前沿领域

量子计算在解决复杂问题和处理大规模数据集方面具有巨大的潜力&#xff0c;远远超过了经典计算机的能力。当与人工智能&#xff08;AI&#xff09;集成时&#xff0c;量子计算可以带来革命性的突破。它的并行处理能力能够在更短的时间内解决更复杂的问题&#xff0c;这对优化和…...

卷积神经网络各层介绍

目录 1 卷积层 2 BN层 3 激活层 3.1 ReLU&#xff08;Rectified Linear Unit&#xff09; 3.2 sigmoid 3.3 tanh&#xff08;双曲正切&#xff09; 3.4 Softmax 4 池化层 5 全连接层 6 模型例子 1 卷积层 卷积是使用一个卷积核&#xff08;滤波器&#xff09;对矩阵进…...

Python应用指南:高德拥堵延时指数

随着城市化进程的加快&#xff0c;交通拥堵问题日益严重&#xff0c;成为影响城市居民生活质量的重要因素之一。为了科学评估和管理交通拥堵&#xff0c;各种交通拥堵指数应运而生。其中&#xff0c;高德地图提供的“拥堵延时指数”因其数据丰富、实时性强和应用广泛而备受关注…...

ISO 21434标准:汽车网络安全管理的利与弊

ISO 21434标准在提升汽车网络安全性方面起到了重要作用&#xff0c;但任何标准都不是完美无缺的&#xff0c;ISO 21434标准也存在一些不足之处。以下是对其不足之处的分析&#xff1a; 一、标准的灵活性与适应性 缺乏具体技术细节&#xff1a;ISO 21434标准更多地提供了网络安…...

无插件H5播放器EasyPlayer.js视频流媒体播放器如何开启electron硬解码Hevc(H265)

在数字化时代&#xff0c;流媒体播放器技术正经历着前所未有的变革。随着人工智能、大数据、云计算等技术的融合&#xff0c;流媒体播放器的核心技术不断演进&#xff0c;为用户提供了更加丰富和个性化的观看体验。 EasyPlayer.js H5播放器&#xff0c;是一款能够同时支持HTTP、…...

excel版数独游戏(已完成)

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

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;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

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

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

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...