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

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...