当前位置: 首页 > 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;但该有的…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...