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

代码随想录阅读笔记-二叉树【二叉搜索树中的搜索】

题目

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

例如,

700.二叉搜索树中的搜索

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

思路

之前我们讲的都是普通二叉树,那么接下来看看二叉搜索树。

大家可以参考这个博客加深对二叉搜索树的理解数据结构——二叉搜索树详解-CSDN博客

二叉搜索树是一个有序树:

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

这就决定了,二叉搜索树,递归遍历和迭代遍历和普通二叉树都不一样。

本题,其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。

递归法

 1、确定递归函数的参数和返回值

递归函数的参数传入的就是根节点和要搜索的数值,返回的就是以这个搜索数值所在的节点。

TreeNode* searchBST(TreeNode* root, int val)

 2、确定终止条件

如果root为空,或者找到这个数值了,就返回root节点。

if (root == NULL || root->val == val) return root;

 3、确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。

因为二叉搜索树的节点是有序的,所以可以有方向的去搜索。

如果root->val > val,搜索左子树,如果root->val < val,就搜索右子树,最后如果都没有搜索到,就返回NULL。

代码如下:

TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;

递归函数的返回值是什么? 是 左子树如果搜索到了val,要将该节点返回。 如果不用一个变量将其接住,那么返回值不就没了。

所以要 result = searchBST(root->left, val)

整体代码如下:

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;TreeNode* result = NULL;if (root->val > val) result = searchBST(root->left, val);if (root->val < val) result = searchBST(root->right, val);return result;}
};

或者我们也可以这么写

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;if (root->val > val) return searchBST(root->left, val);if (root->val < val) return searchBST(root->right, val);return NULL;}
};
迭代法

一提到二叉树遍历的迭代法,可能立刻想起使用栈来模拟深度遍历,使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了,因为二叉搜索树的特殊性,也就是节点的有序性,可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树,递归过程中还有回溯的过程,例如走一个左方向的分支走到头了,那么要调头,在走右分支。

对于二叉搜索树,不需要回溯的过程,因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为3的节点,我们不需要搜索其他节点,也不需要做回溯,查找的路径已经规划好了。

中间节点如果大于3就向左走,如果小于3就向右走,如图:

二叉搜索树

所以迭代法代码如下:

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root != NULL) {if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return NULL;}
};

相关文章:

代码随想录阅读笔记-二叉树【二叉搜索树中的搜索】

题目 给定二叉搜索树&#xff08;BST&#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 NULL。 例如&#xff0c; 在上述示例中&#xff0c;如果要找的值是 5&#xff0c;但因为没有节点…...

1、初识drf

drf的学习需要学习者有django基本使用知识。 文章目录 什么是drf&#xff0c;有什么作用CBV是什么初步使用drf 下载以及django创建项目django最小启动内容修改setting修改 url 编写drf视图编辑url测试返回结果 什么是drf&#xff0c;有什么作用 drf(django rest-framework),让…...

速盾:cdn高防御服务器租用有哪些好处

随着互联网的发展&#xff0c;网络安全问题日益突出。攻击者利用各种手段不断对网站进行攻击&#xff0c;给网站的安全运行带来威胁。为了保障网站的正常运行和数据的安全&#xff0c;越来越多的网站开始租用CDN高防御服务器。那么&#xff0c;租用CDN高防御服务器有哪些好处呢…...

【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权限

系列文章目录 【跟小嘉学 Linux 系统架构与开发】一、学习环境的准备与Linux系统介绍 【跟小嘉学 Linux 系统架构与开发】二、Linux发型版介绍与基础常用命令介绍 【跟小嘉学 Linux 系统架构与开发】三、如何查看帮助文档 【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权…...

ubuntu18.04图形界面卡死,鼠标键盘失灵, 通过MAC共享网络给Ubuntu解决!

ubuntu18.04图形界面卡死&#xff0c;鼠标键盘失灵&#xff0c; 通过MAC共享网络给Ubuntu解决&#xff01; 1. 尝试从卡死的图形界面切换到命令行界面2. 进入bios和grub页面3. 更改Grub中的设置&#xff0c;以进入命令行4. 在命令行页面解决图形界面卡死的问题5. Mac共享WI-FI网…...

ESG认证(ESG=环境、社会和治理 Environmental, Social, and Governance)

什么是ESG认证 ESG认证是指根据企业在环境、社会和治理&#xff08;Environmental, Social, and Governance&#xff09;方面的表现而设立的一种评价或评级体系。 环境&#xff08;Environmental&#xff09;&#xff1a;这一维度关注企业如何管理其对环境的影响&#xff0c;包…...

Cesium Viewer 类学习

Viewer提供了创建和控制3D场景所需的所有基本功能&#xff0c;包括加载3D模型、添加图像覆盖物、设置相机位置和方向、处理用户输入等。 构造函数&#xff1a; new Cesium.Viewer(container, options) 是用来创建一个新的 Cesium 视图器&#xff08;Viewer&#xff09;实例的…...

第十四届省赛大学B组(C/C++)子串简写

原题链接&#xff1a;子串简写 程序猿圈子里正在流行一种很新的简写方法&#xff1a; 对于一个字符串&#xff0c;只保留首尾字符&#xff0c;将首尾字符之间的所有字符用这部分的长度代替。 例如 internationalization 简写成 i18n&#xff0c;Kubernetes 简写成 K8s&#…...

深入浅出 -- 系统架构之微服务架构

1.1 微服务的架构特征&#xff1a; 单一职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责 自治&#xff1a;团队独立、技术独立、数据独立&#xff0c;独立部署和交付 面向服务&#xff1a;服务提供统一标准的接口&…...

YoloV8改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图

摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我…...

Python从0到100(十):Python集合介绍及运用

一、集合定义 定义&#xff1a; 由不同元素组成的集合&#xff0c;集合是一组无序排列 可hash值&#xff0c;可作为字典的key。 特性&#xff1a; 集合的目的是将不同的值存放在一起&#xff0c;不同的集合间用来做关系运算&#xff0c;无须纠结于集合中的单个值。 &#xff0…...

实用技巧:如何取消app的截屏禁用

因为我想要在小鹅通App做笔记,但是被小鹅通App禁用截屏了,这真是一个很糟糕的使用体验,虽然可能是为了保护商家权益…… 方法1 可以让商家设置课程可以截屏 方法2 手机root,安装Xposed框架,利用Xposed框架上面的插件我们可以对手机进行高度定制化,而安装Xposed框架的…...

【氮化镓】GaN SP-HEMT的栅极可靠性

概括总结&#xff1a; 本文研究了氮化镓&#xff08;GaN&#xff09;肖特基型p-栅高电子迁移率晶体管&#xff08;GaN SP-HEMT&#xff09;的栅极鲁棒性和可靠性&#xff0c;通过一种新的电路方法评估了在实际转换器中栅极电压&#xff08;VGS&#xff09;过冲波形的栅极电压应…...

Linux基础和进阶用法

Linux是一个广泛使用的开源操作系统&#xff0c;下面是一些Linux基础用法的详细介绍&#xff1a;文件和目录操作&#xff1a;ls&#xff1a;列出文件和目录的详细信息&#xff0c;包括权限、所有者、大小等。cd&#xff1a;切换到指定目录。使用cd ~返回用户主目录&#xff0c;…...

Linux运维-SHELL编程之正则表达式与流编辑处理器

Linux运维-SHELL编程之正则表达式与流编辑处理器 什么是正则表达式 正则表达式是一种用来描述字符序列的强大工具&#xff0c;通常用于字符串的匹配、搜索和替换操作。它由普通字符&#xff08;例如字母、数字&#xff09;和特殊字符&#xff08;称为元字符&#xff09;组成&…...

openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint

文章目录 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint256.1 功能描述256.2 语法格式256.3 参数说明 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint 256.1 功能描述 设置本次查询执行内生效的…...

flex:1的作用是什么?

占满剩余的高度 <div classfather><div classson1></div><div classson2></div> </div>当给father添加display:flex之后&#xff0c;假设给son2添加flex:1&#xff0c;那么son2将会占满除son1之外的高度...

Mysql安装(命令方式安装)

下载mysql压缩包 Mysql可以使用界面安装&#xff0c;也可以使用命令的方式安装&#xff0c;今天我们使用命令的方式安装mysql。首先下载mysql压缩包&#xff08;下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/&#xff09;&#xff0c;解压到你想要安装的目录。 …...

Vben Admin实战-系统管理之用户管理-(第12节)

系列文章目录 第一节:Vben Admin介绍和初次运行 第二节:Vben Admin 登录逻辑梳理和对接后端准备 第三节:Vben Admin登录对接后端login接口 第四节:Vben Admin登录对接后端getUserInfo接口 第五节:Vben Admin权限-前端控制方式 第六节:Vben Admin权限-后端控制方式 第七节…...

Oracle常规操作

1、查看用户和密码 select username,password from dba_users; --修改用户和密码 alter user system identified by manager; alter user system identified by values 2D594E86F93B17A1; --解锁用户 alter user system account unlock; -- 用SYSDBA身份进入数据库,然…...

「33」如何让你的直播场景增加透视感?

「33」模糊滤镜增强背景画面透视感 在直播中,背景一直是作为一种陪衬而存在的,位于主场景的后面,其实,说得更直白一些,背景的存在就犹如“绿叶”,是为了衬托红花更加艳丽。所以…… 你通过画面背景的调整,可以从整体上对视频或图片的画面进行装饰,有助于增加画面的空间…...

Macbook文件清理软件 Mac电脑清理垃圾文件怎么清理

为了维护Macbook电脑的系统健康&#xff0c;我们需要定期给电脑进行全面清理&#xff0c;清除系统垃圾文件、软件缓存和系统内存。那么好用的Macbook文件清理软件有哪些呢&#xff1f;今天就给大家介绍几款好用的电脑清理软件并介绍Mac电脑清理垃圾文件怎么清理。 一、Macbook…...

【Java基础】Java基础知识整合

文章目录 1. 转义字符2. 变量2.1 字符串与整型相加2.2 byte和short的区别2.3 float和double的区别2.4 char类型2.5 boolean类型2.6 自动类型转换及运算2.7 强制类型转换2.8 String的转换2.9 除法运算2.10 取模规则 3. 自增4. 逻辑运算符5. 赋值运算 6. 三元运算符&#xff1a;7…...

构建集创建、售卖、转让于一体,且基于ERC721 token的NFT平台,从编写智能合约开始(Web3项目四实战之一)

NFT 全称是 non-fungible token(非同质化代币或不可篡改代币)是记录在区块链上的唯一数字标识符,用于证明所有权和真实性。NFT 的所有权记录在区块链中,所有者可以转让,从而允许 NFT 出售和交易。任何人都可以创建 NFT,创建 NFT 几乎不需要任何编码技能。NFT 通常包含对艺…...

跨境金融区块链服务平台

跨境金融服务是因企业及个人跨境经营、交易、投资、往来等活动而产生的资金使用、调拨、配置等需求&#xff0c;而提供的金融服务。近年来&#xff0c;随着我国经济的快速稳步增长和全球化经济一体化的不断深入发展&#xff0c;跨境金融业务增长迅速&#xff0c;监管也开始转化…...

运筹学经典问题(八):CVRP和VRP-TW

文章目录 问题描述问题建模决策变量数学建模基于容量的消除子环的约束 &#xff08;load-based SECs&#xff09; CVRP完整的数学模型加上时间窗限制的CVRP 问题描述 给定一个图&#xff0c;图上的点代表客户&#xff0c;边代表客户之间的路线&#xff0c;边的权重代表客户之间…...

AI与技术美术(TechArt)

AI技术与TA 人工智能&#xff08;AI&#xff09;技术在技术美术&#xff08;TechArt&#xff09;领域的应用&#xff0c;为创业者开辟了一片新的天地。技术美术作为一个跨学科领域&#xff0c;融合了传统美术和现代技术&#xff0c;特别是AI技术&#xff0c;以创造新型的艺术表…...

二叉树层序遍历 及相关题目

1&#xff0c;力扣102 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;[[3],[9,20],[15,7]]示例…...

【前端面试3+1】11 http和https有何不同及https的加密过程、数组有哪些方法及作用、tcp三次握手四次挥手、【分发饼干】

一、http和https有何不同&#xff1f;https的加密过程 1、不同&#xff1a; HTTP和HTTPS的主要区别在于安全性。HTTP是超文本传输协议&#xff0c;是一种用于传输数据的协议&#xff0c;但是传输的数据是明文的&#xff0c;容易被窃听和篡改。而HTTPS是在HTTP基础上加入了SSL/T…...

替代 Redis 和 Memcached:25 倍吞吐量! | 开源日报 No.213

dragonflydb/dragonfly Stars: 22.4k License: NOASSERTION Dragonfly 是一个内存数据存储&#xff0c;适用于现代应用工作负载&#xff0c;可替代 Redis 和 Memcached。与传统的内存数据存储相比&#xff0c;Dragonfly 提供了 25 倍的吞吐量、更高的缓存命中率和更低尾部延…...

网站设置了自动登录怎么显示密码/最有效的15个营销方法

首先去官网下载MySQLhttps://dev.mysql.com/downloads/mysql/5.7.html#downloads我是下载的5.7.23 zip版本&#xff0c;解压到C:\mysql-5.7.23-winx64然后配置环境变量&#xff1a;变量名&#xff1a;MYSQL_HOME变量值&#xff1a;C:\mysql-5.7.23-winx64在Path变量值最前面添加…...

建设网站需要哪些人/网页设计代码

学习了一下费用流的做法&#xff0c;顺便学习了一下zkw&#xff08;听说原始对偶是折中做法&#xff0c;这种没什么特点的就不学了&#xff09;&#xff0c;顺便研究了一下费用流的速度&#xff1a;&#xff08;对于这题而言&#xff09;upd抱歉我这个SLF优化写反了。。。然而反…...

自媒体营销推广方案/seo是搜索引擎优化

刚才遇到一个问题&#xff0c;刚刚解决&#xff0c;觉得有必要记录一下。 问题是这样的&#xff1a;后台传到jsp上一个将List转化成JSON串的字符串&#xff0c;而原先的List中放入的是Map元素。将这个JSON串打印出来结果如下&#xff1a; [{"f0":"7908",&q…...

万维网的代表网站/营销软文小短文

如果需要查看一段时间内的结果、对比不同数据集的结果,或展示单个元素对汇总量的贡献和影响,则条形图会很有用处。 默认情况下,条形图会将一个向量或矩阵中的每个元素表现为一个条形,条形的高度与元素的值成比例。 二维条形图 bar 函数沿着 x 轴分布条形。同一行的矩阵元素…...

不用vip的免费追剧软件/防城港网站seo

每次使用etcdctl&#xff0c;都要长长的一大串&#xff0c;太麻烦了&#xff0c;直接把变量写入文件中&#xff0c;就方便很多了 vi ~/.bashrc 行尾添加 export ETCDCTL_ENDPOINTShttps://127.0.0.1:2379export ETCDCTL_CACERT/etc/kubernetes/pki/etcd/ca.crtexport ETCDCTL_C…...

网站开发协议/宣传软文模板

一新建用户 ----------- 二首先修改权限必须在电脑cmd 中运行 开设的权限 主要就是 1 所有库的 *.* 2 所有的表 db.* 3所有的字段db.t1 4 很对一个字段 1开启第一个cmd 利用root 用户名 增加用户的权限 实例select 增加的用户 只能查 不能修改 2 开…...