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

算法通关村第九关——中序遍历与搜索树

1 中序遍历和搜索树原理

二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是:

  • 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值;
  • 若它的右子树不为空,则右子树所有节点的值均大于它的根节点的值;
  • 它的左、右子树也分别为二叉搜索树,比如下面的例子:

在这里插入图片描述

这两棵树的中序遍历分别是[1, 2, 3, 4, 5, 6, 7, 8, 9][6, 7, 8, 9],都是二叉搜索树。

2 二叉搜索树中搜索特定值

力扣700题,给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

比如target为3,给定二叉搜索树:

			5/  \3    4/ \1   2

应该返回如下子树:

		  3  / \1   2

2.1 递归实现

使用递归来实现,先来分析一下有哪些情况:

  • 如果根节点root === null或者root.val === target就直接返回根节点;
  • 如果target < root.val,说明比右子树的值小,去根节点的左子树进行查找searchBST(root.left, target);
  • 如果target > root.val,说明比左子树的值大,去根节点的右子树进行查找searchBST(root.right, target)

递归完整代码如下:

// 递归法
function searchBST(root, target) {// 如果根节点为空或者root.val === target,直接返回rootif (root === null || root.val === target) {return root;}// 如果target < root.val,进入根节点的左子树查找// 如果target > root.val,进入根节点的右子树查找return target < root.val ? searchBST(root.left, target) : searchBST(root.right, target);
}

2.2 迭代实现

迭代逻辑:

  • 如果根节点root === null或者root.val !== target,进入下面的判断
    • 如果target < root.val,说明比右子树的值小,去根节点的左子树进行查找,root = root.left;
    • 如果target > root.val,说明比左子树的值大,去根节点的右子树进行查找,root = root.right

迭代完整代码如下:

// 迭代法
function searchBST(root, target) {// 如果根节点为空或者target !== root.valwhile (root !==null && target !== root.val) {// 如果target < root.val,进入根节点的左子树查找,root = root.left// 如果target > root.val,进入根节点的右子树查找,root = root.rightroot = (target < root.val ? root.left : root.right);}return root;
}

3 验证二叉搜索树

力扣98题,给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。有效二叉树定义如下:

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

分析:根据题目以及中序遍历的特性,可以知道二叉搜索树中序遍历得到的序列是一个升序序列,要判断是否是一个有效二叉树,只需要在中序遍历的时候一边遍历一边检查当前节点的值是否大于前一个遍历到的节点值即可。

3.1 递归实现

递归实现,代码如下:

function isValidBST(root) {let pre = Number.MIN_SAFE_INTEGER;return validBST(root);function validBST(node) {if (node === null) {return true;}// 如果左子树某个元素不满足要求就退出if (!validBST(node.left)) {return false;}// 如果当前节点值≤中序遍历前一个节点的值,不能满足二叉搜索树条件if (node.val <= pre) {return false;}pre = node.val;return validBST(node.right);}
}

3.2 迭代实现

测试用例的最小节点有可能是javascript中的最小值,因此初始化preVal = -Infinity

function isValidBST(root) {const nodeStack= [];let preVal = -Infinity;while (nodeStack.length !== 0 || root !== null) {while (root !== null) {nodeStack.push(root);// 先遍历左子树root = root.left;}// 比较左子树中间根节点与前一个节点的值,如果小与前一个节点值,说明不是二叉搜索树root = nodeStack.pop();if (root.val <= preVal) {return false;}preVal = root.val;// 再遍历右子树root = root.right;}return true;
}

相关文章:

算法通关村第九关——中序遍历与搜索树

1 中序遍历和搜索树原理 二叉搜索树按照中序遍历正好是一个递增序列。其比较规范的定义是&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值均小于它的根节点的值&#xff1b;若它的右子树不为空&#xff0c;则右子树所有节点的值均大于它的根节点的值&…...

测试框架pytest教程(5)运行失败用例-rerun failed tests

# content of test_50.py import pytestpytest.mark.parametrize("i", range(50)) def test_num(i):if i in (17, 25):pytest.fail("bad luck") 运行这个文件&#xff0c;2个失败&#xff0c;48个通过。 要运行上次失败的测试用例&#xff0c;可以使用--l…...

【车载开发系列】UDS当中的时间参数

【车载开发系列】UDS当中的时间参数 UDS当中的时间参数 【车载开发系列】UDS当中的时间参数一. 术语定义二. 网络层时间调整参数三. ECU诊断层与会话层参数 一. 术语定义 缩写全称中文说明BSBlock Size块大小STminSeparation time min时间间隙SIService Identifier服务标识符S…...

PDF中的表格怎么转换为Excel?这两个工具一定得收藏!

PDF是一种常见的文件格式&#xff0c;它可以保持文件的原始样式和内容&#xff0c;但是也有一些缺点&#xff0c;比如不易编辑和处理数据。如果你想要将PDF中的表格或数据导出到Excel中&#xff0c;以便进行分析、计算或制作图表&#xff0c;那么你可能需要一个专业的PDF转Exce…...

ssh scp sshpass

ssh命令用于远程连接主机 ssh usernamehostname更多用法参考&#xff1a; ssh常用用法 scp 命令是用于通过 SSH 协议安全地将文件复制到远程系统和从远程系统复制文件到本地的命令 比如&#xff1a; scp /data/log/a.txt root192.168.1.100:/data/log该命令就就将本地的a.t…...

leetcode 1996. 游戏中弱角色的数量(排序的魅力)

题目 题意: 给定n个人的攻击力和防御力&#xff0c;对于一个人来说&#xff0c;如果存在某个人的攻击力和防御力都比他高&#xff0c;那么称这个人为弱角色。统计弱角色的数量 思路: 排序&#xff0c;攻击力按从大到小排序&#xff0c;这样遍历的时候某个数时前边的攻击力都比他…...

从头到尾说一次 Spring 事务管理(器) | 京东云技术团队

事务管理&#xff0c;一个被说烂的也被看烂的话题&#xff0c;还是八股文中的基础股之一。​ 本文会从设计角度&#xff0c;一步步的剖析 Spring 事务管理的设计思路&#xff08;都会设计事务管理器了&#xff0c;还能玩不转&#xff1f;&#xff09; 为什么需要事务管理&…...

php 系列题目,包含查看后端源代码

一、弱类型比较问题 原则&#xff1a; 1.字符串和数字比较&#xff0c;字符串回被转换成数字。 "admin" 0&#xff08;true) admin被转换成数字&#xff0c;由于admin是字符串&#xff0c;转换失败&#xff0c;变成0 int(admin)0,所以比较结果是ture 2.混合字符串转…...

令牌桶C语言代码实现

令牌桶实例 令牌桶三要素 cps 每秒钟传输字节数 burst 令牌桶内最多能传输的字节数&#xff0c;token的最大值 token 令牌的个数 之前是一个令牌(token)对应一个字节&#xff0c;现在将一个token变为一个cps&#xff0c;cps是解码速率&#xff0c;每攒到一个令牌&#xff…...

Mybatis 建立依赖失败:报错Dependency ‘mysql:mysql-connector-java:8.0.28‘ not found

Mybatis 建立依赖失败&#xff1a;报错Dependency ‘mysql:mysql-connector-java:8.0.28’ not found 解决办法&#xff1a; 写完依赖代码&#xff0c;直接重构&#xff0c;下载依赖。 图片: ![Alt](https://img-home.csdnimg.cn/images/20220524100510.png Mac 版本注意Ide…...

多线程+隧道代理:提升爬虫速度

在进行大规模数据爬取时&#xff0c;爬虫速度往往是一个关键问题。本文将介绍一个提升爬虫速度的秘密武器&#xff1a;多线程隧道代理。通过合理地利用多线程技术和使用隧道代理&#xff0c;我们可以显著提高爬虫的效率和稳定性。本文将为你提供详细的解决方案和实际操作价值&a…...

使用@Configuration和@Bean给spring容器中注入组件

Confguration->告诉spring这是一个配置类 以前我们是使用配置文件来注册bean的&#xff0c;现如今可以用Configuration 来代替配置文件。 //配置配配置文件 Configuration // 告诉Spring这是一个配置类,等同于以前的配置文件 public class MainConfig {// Bean注解是给IOC…...

信号波形解读

can波形解读 实际波形 标准帧 发送数据 仲裁段 0x1AA 数据长度为8字节 内容为&#xff1a;0x41, 0x20, 0x38, 0x41, 0x00, 0x16, 0x00, 0x00 波特率 111K...

Centos 解决 XXX不在 sudoers 文件中。此事将被报告。的错误

本来想使用 sudo 拷贝一个文件&#xff0c;结果出现上面的问题&#xff01; 下面是解决方法&#xff1a; 首先登录root&#xff0c;然后执行下面的命令 vim /etc/sudoers 将你需要添加的用户带红色框线的地方&#xff0c;模仿root写一遍&#xff0c;然后保存&#xff01; …...

雪花算法和uuid的区别

雪花算法&#xff08;Snowflake Algorithm&#xff09;和 UUID&#xff08;Universally Unique Identifier&#xff09;都是用于生成唯一标识符的方法&#xff0c;但它们在实现和适用场景上存在一些区别。 雪花算法&#xff1a; 雪花算法是Twitter开发的一种分布式ID生成算法…...

docker之DockerFile与网络

目录 DockerFile 构建步骤 基础知识 指令 实战&#xff1a;构建自己的centos 第一步&#xff1a;编写dockerfile文件 第二步&#xff1a;构建镜像文件 docker网络 原理 功能 网络模式 host模式 container模式 none模式 bridge模式 DockerFile dockerfile 是用来…...

知识蒸馏开山之作(部分解读)—Distilling the Knowledge in a Neural Network

1、蒸馏温度T 正常的模型学习到的就是在正确的类别上得到最大的概率&#xff0c;但是不正确的分类上也会得到一些概率尽管有时这些概率很小&#xff0c;但是在这些不正确的分类中&#xff0c;有一些分类的可能性仍然是其他类别的很多倍。但是对这些非正确类别的预测概率也能反…...

centos 7 安装 docker-compose curl 设置代理

sudo curl -x “http://192.168.1.2:3128” 需要验证的代理 sudo curl -x “http://username:password192.168.1.2:3128” 1.下载 sudo curl -L "https://github.com/docker/compose/releases/download/1.23.2/docker-compose-$(uname -s)-$(uname -m)" -o /usr/lo…...

3D姿态相关的损失函数

loss_mpjpe: 计算预测3D关键点与真值之间的平均距离误差(MPJPE)。 loss_n_mpjpe: 计算去除尺度后预测3D关键点误差(N-MPJPE),评估结构误差。 loss_velocity: 计算3D关键点的速度/移动的误差,评估运动的平滑程度。 loss_limb_var: 计算肢体长度的方差,引导生成合理的肢体长度…...

ChatGPT取代人类仍然是空想?有没有一种可能是AI在迷惑人类

ChatGPT自从去年发布以来&#xff0c;就掀起了这些大语言模型将如何颠覆一切的激烈讨论&#xff0c;从为学生写作文、输出SEO文章&#xff0c;甚至取代谷歌成为世界上最受欢迎的搜索引擎&#xff0c;影响领域无所不包&#xff0c;甚至可能取代编剧、小说家和音乐家等从事创意工…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

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

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

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...