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

LeetCode 700.二叉搜索树中的搜索

LeetCode 700.二叉搜索树中的搜索

1、题目

题目链接:700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

示例 1:
image.png

输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]

示例 2:
image.png

输入:root = [4,2,7,1,3], val = 5
输出:[]

提示:

  • 树中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

2、递归

思路

二叉搜索树是一个有序树,满足以下性质:

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

据此可以得到如下算法:
若 root 为空则返回空节点;
若 val = root.val,则返回 root;
若 val < root.val,递归左子树;
若 val > root.val,递归右子树。

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

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

TreeNode* searchBST(TreeNode* root, int val)
  1. 确定终止条件

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

if (root == nullptr || root->val == val) {return root;
}
  1. 确定单层递归的逻辑

看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的,所以可以有方向的去搜索。
如果root->val > val,搜索左子树,如果root->val < val,就搜索右子树,最后如果都没有搜索到,就返回 nullptr。
代码如下:

TreeNode* result = nullptr;
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 == nullptr || root->val == val) {return root;}// 如果根节点的值大于目标值,则在左子树中继续搜索if (root->val > val) {return searchBST(root->left, val);} else {// 如果根节点的值小于目标值,则在右子树中继续搜索return searchBST(root->right, val);}}
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

3、迭代法

思路

我们将方法一的递归改成迭代写法:
若 root 为空则跳出循环,并返回空节点;
若 val=root.val,则返回 root;
若 val<root.val,将 root 置为 root.left;
若 val>root.val,将 root 置为 root.right。

代码

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

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

相关文章:

LeetCode 700.二叉搜索树中的搜索

LeetCode 700.二叉搜索树中的搜索 1、题目 题目链接&#xff1a;700. 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则…...

程序设计实践-课程设计任务布置(麦当劳) (price 200)(不包含文档)

WX: help-assignment code price 200&#xff08;不包含文档&#xff01;不包含文档&#xff01;不包含文档&#xff01;&#xff09; 课题任务-概述 2023年5月&#xff0c;麦当劳在北邮开业。大量的学生去那里订餐。正因为如此&#xff0c;麦当劳的在线点餐系统经常关闭以避…...

leetcode 918.环形子数组的最大和

思路&#xff1a;DP 其实和昨天做的哪个重复数组差不多&#xff0c;按顺序来说先做这个题目其实更好。 这里需要分两种情况&#xff1a;第一个&#xff0c;就是数组不越界的时候&#xff0c;这个时候最大子数组和就是leetcode 53题的题解。 如果说越界了&#xff0c;我们还需…...

Spring中用到的设计模式有哪些

工厂模式,BeanFactory就是简单工厂模式的体现,根据传入一个唯一的标识来获得Bean对象。 单例模式,Spring依赖注入Bean实例默认是单例的。Spring依赖注入(包括lazy-init方式)都是发生在AbstractBeanFactory的getBean里。getBean的doGetBean方法调用getSingleton进行bean的创…...

CSS 样式清单整理:文字超出部分显示省略号和设置placeholder的字体样式

单行文本的溢出显示省略号&#xff08;一定要有宽度&#xff09; p{width:200rpx;overflow: hidden;text-overflow:ellipsis;white-space: nowrap;}多行文本溢出显示省略号 p {display: -webkit-box;-webkit-box-orient: vertical;-webkit-line-clamp: 3;overflow: hidden;}设…...

Docker容器:Docker-Consul 的容器服务更新与发现

目录 前言 一、什么是服务注册与发现 二、 Docker-Consul 概述 1、Consul 概念 2、Consul 提供的一些关键特性 3、Consul 的优缺点 4、传统模式与自动发现注册模式的区别 4.1 传统模式 4.2 自动发现注册模式 5、Consul 核心组件 5.1 Consul-Template组件 5.2 Consu…...

容器化Jenkins远程发布java应用(方式二:自定义镜像仓库远程拉取构建)

1.创建maven项目 2.配置git、maven 3.阿里控制台>容器镜像服务>镜像仓库>创建镜像仓库 4.执行shell脚本&#xff08;推送镜像到阿里云镜像仓库&#xff09; 使用到登录阿里云仓库命令 #!/bin/bash # 服务名称 SERVER_NAMEplanetflix-app # 镜像tag IMAGE_TAG1.0.0-SN…...

解密某游戏的数据加密

前言 最近有个兄弟通过我的视频号加我&#xff0c;咨询能否将这个dubo游戏游戏开始前就将数据拿到从而进行押注&#xff0c;于是通过抓包工具测试了下&#xff0c;发现数据有时候是明文&#xff0c;有时候确实密文&#xff0c;大致看了下有这几种加密&#xff1a;Md5aes、Md5&a…...

【报错合集】完美解决“虚拟机使用的是此版本 VMware Workstation 不支持的硬件版本”

文章目录 解决方案&#xff1a;更改设置的硬件版本 今天我需要将别人的虚拟机克隆到我的VMware Workstation上运行&#xff0c;结果发生了以下的错误&#xff1a; 刚开始以为是VMware Workstation的版本问题太低导致的&#xff0c;所以我删除了原来的那个版本&#xff0c;下载…...

YOLOv8小白中的小白安装环境教程!没一个字废话,看一遍不踩坑!

文章目录 去哪里下代码?怎么下代码?怎么装环境?命令行界面(CLI)指令和Python脚本区别?附录1 conda常用指令附录2 git常用指令附录3 项目代码文件作用去哪里下代码? 下载代码请大家直接去 YOLOv8的官方仓库下载,名字叫 ultralytics,有些镜像网站和个人发的等来历不明的代…...

C#正则表达式,提取信息使用

正则表达式简介 在C#中&#xff0c;正则表达式&#xff08;Regular Expression&#xff0c;通常简写为regex或regexp&#xff09;是一种功能强大的文本处理工具&#xff0c;它使用特定的字符序列来定义搜索模式&#xff0c;从而实现对文本的高效搜索、匹配和替换操作。正则表达…...

【数据结构】详解队列

现在我们来掌握一下队列&#xff01;如果有对往期知识有不足地方&#xff0c;可翻阅之前文章哦&#xff01; 个人主页&#xff1a;小八哥向前冲~-CSDN博客 所属专栏&#xff1a;数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客 栈和队列的实现其实都是对你顺序表和链表的检验…...

大模型微调方法汇总

微调方法 Freeze方法P-tuning方法 prefix-tuningPrompt TuningP-tuning v1P-tuning v2Lora方法 重要相关参数LoRA 的优势Qlora方法 相关参数微调经验 模型选择模型大小选择数据处理微调方案英文模型需要做词表扩充吗&#xff1f;如何避免灾难遗忘大模型的幻觉问题微调后的输出…...

探究NVMe SSD HMB应用场景与影响-<续>

如果需要采用HMB功能&#xff0c;需要SSD支持NVME协议且NVMe 1.2及以上版本。NVME协议中对HMB对应有2个关键参数&#xff1a; HMB建议值&#xff08;HMPRE&#xff09;&#xff1a;设定实际分配给HMB使用的主机内存容量&#xff0c;为设备提供最优性能的内存分配量。 HMB最小值…...

YTU 3166 共享单车 DFS 记忆化搜索

问题 D: 共享单车 题目描述 共享单车走进烟台&#xff0c;小明决定尝试。小明启动共享单车 App&#xff0c;轻松地找到附近的单车。那么问题来了&#xff0c;到最近的那辆单车&#xff0c;小明大约要走多少米呢&#xff1f; 现在简化问题。将地图设定成一个由 100100 米的像…...

RAG应用中的路由模式

依据的用户查询意图在 RAG 应用程序使用“路由控制模式”可以帮助我们创建更强大的 RAG 应用程序。我们通常希望用户能够访问的数据可以来自各种来源,如报告、文档、图片、数据库和第三方系统。 对于基于业务的 RAG 应用程序,我们可能还希望用户能够与其它业务系统进行交互,…...

运维:SSH常用命令简介

SH&#xff0c;全称为Secure Shell&#xff0c;是建立在应用层和传输层基础上的安全协议。SSH 是目前较可靠&#xff0c;专为远程登录会话和其他网络服务提供安全性的协议。利用 SSH 协议可以有效防止远程管理过程中的信息泄露问题。通过 SSH 可以对所有传输的数据进行加密&…...

Springboot+Vue项目-基于Java+MySQL的流浪动物管理系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…...

力扣刷题:四数相加Ⅱ

题目详情&#xff1a; 解法一&#xff1a;暴力枚举 对于这道题&#xff0c;我们的第一思路就是暴力枚举&#xff0c;我们可以写一个四层的for循环进行暴力匹配&#xff0c;只要相加的结果等于0就进行统计。但是我们会发现&#xff0c;我们的事件复杂度为O(N^4)事件复杂度非常大…...

如果通过Glide 设置图片圆角

要给图片设置一个圆角,通常方法是在ImageView 标签外添加一个CardView 标签,然后设置圆角值,但是今天遇到一个问题就是 RecyclerView Item 中这样操作的话会遇到这样的一个报错: Cannot call this method while RecyclerView is computing a layout or scrolling androidx.rec…...

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

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

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

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

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...

工厂方法模式和抽象工厂方法模式的battle

1.案例直接上手 在这个案例里面&#xff0c;我们会实现这个普通的工厂方法&#xff0c;并且对比这个普通工厂方法和我们直接创建对象的差别在哪里&#xff0c;为什么需要一个工厂&#xff1a; 下面的这个是我们的这个案例里面涉及到的接口和对应的实现类&#xff1a; 两个发…...