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

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

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

难度:easy\color{Green}{easy}easy
难度:middle\color{orange}{middle}middle
难度:hard\color{red}{hard}hard


题目描述

给定二叉搜索树(BST)的根节点 rootrootroot 和一个整数值 valvalval

你需要在 BST 中找到节点值等于 valvalval 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 nullnullnull

示例 1:

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

示例 2:

[外链图片转存中…(img-QAZGWobk-1677565545106)]

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

提示:

  • 数中节点数在 [1,5000][1, 5000][1,5000] 范围内
  • 1<=Node.val<=1071 <= Node.val <= 10^{7}1<=Node.val<=107
  • rootrootroot 是二叉搜索树
  • 1<=val<=1071 <= val <= 10^{7}1<=val<=107

算法1

(递归)

二叉搜索树满足如下性质:

  • 左子树所有节点的元素值均小于根的元素值;
  • 右子树所有节点的元素值均大于根的元素值。

据此可以得到如下算法:

  • 若 root 为空则返回空节点;
  • 若 val=root.val,则返回 root;
  • 若 val<root.val,递归左子树;
  • 若 val>root.val,递归右子树。

复杂度分析

  • 时间复杂度O(n)O(n)O(n),其中 nnn 是二叉搜索树的节点数。

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

C++ 代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (!root) return NULL;if (root->val == val) return root;if (root->val > val) return searchBST(root->left, val);else return searchBST(root->right, val);}
};

算法2

(迭代)

二叉搜索树满足如下性质:

  • 左子树所有节点的元素值均小于根的元素值;
  • 右子树所有节点的元素值均大于根的元素值。

据此可以得到如下算法:

  • 若 root 为空则跳出循环,并返回空节点;
  • 若 val=root.val,则返回 root;
  • 若 val<root.val,将 root 置为 root.left;
  • 若 val>root.val,将 root 置为 root.right。

复杂度分析

  • 时间复杂度O(n)O(n)O(n),其中 nnn 是二叉搜索树的节点数。

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

C++ 代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root) {if (root->val == val) return root;else if (root->val > val) root = root->left;else root = root->right;}return nullptr;}
};

相关文章:

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

LeetCode 700. 二叉搜索树中的搜索 难度&#xff1a;easy\color{Green}{easy}easy 难度&#xff1a;middle\color{orange}{middle}middle 难度&#xff1a;hard\color{red}{hard}hard 题目描述 给定二叉搜索树&#xff08;BST&#xff09;的根节点 rootrootroot 和一个整数值…...

【数据结构】树与二叉树

目录 1、树的概念及结构 1.1、概念 1、树的特点 2、树与非树 1.2、概念 &#xff08;重要&#xff09; 1.3、树的表示形式 2、二叉树&#xff08;重点&#xff09; 2.1、概念 2.2、二叉树的特点 2.3、两种特殊的二叉树 1、满二叉树 2、完全二叉树 2.4、二叉树的性…...

Stress压力工具的部署及使用

Stress压力工具的部署及使用 下载地址&#xff1a;wget https://fossies.org/linux/privat/old/stress-1.0.5.tar.gz 1.部署 进入目录执行./autogen.sh [rootiZ2ze1pj93eyq389c2ppi5Z stress-1.0.5]# ./autogen.sh ps&#xff1a;如果执行过程中缺包&#xff0c;安装对应的…...

[蓝桥杯 2020 省 AB3] 乘法表

题目描述九九乘法表是学习乘法时必须要掌握的。在不同进制数下&#xff0c;需要不同的乘法表。例如, 四进制下的乘法表如下所示&#xff1a;1*11 2*12 2*210 3*13 3*212 3*321请注意&#xff0c;乘法表中两个数相乘的顺序必须为样例中所示的顺序&#xff0c;不能随意交换两个乘…...

Python基础知识

基础知识 基础知识包括输入输出、变量、数据类型、表达式、运算符这5个方面。 1.输入输出 Python有很多函数&#xff0c;后面我们会细讲&#xff0c;但这里先将两个最基本的函数&#xff1a;输入和输出。 输出函数print()&#xff0c;在前面我们已经用过了&#xff0c;语法…...

FME案例实战教程:聚焦实战应用,摆脱思路束缚,您值得拥有

一、教程链接&#xff08;一&#xff09;FME案例实战教程链接1.FME案例实战教程&#xff08;完整版&#xff09; ☚强烈推荐☚2.FME案例实战教程&#xff08;A组&#xff09;3.FME案例实战教程&#xff08;B组&#xff09;4.FME案例实战教程&#xff08;C组&#xff09;&#…...

【JavaScript】根据元素内容遍历元素的方案

▒ 目录 ▒&#x1f6eb; 导读需求1️⃣ jQuery2️⃣ XPATH&#xff08;document.evaluate&#xff09;3️⃣ 原生js&#xff08;querySelectorAll & Array&#xff09;&#x1f6ec; 文章小结&#x1f4d6; 参考资料&#x1f6eb; 导读 需求 因业务需要&#xff0c;根据元…...

kafka全解

目录Kafka概述定义消息队列目录结构分析传统消息队列的应用场景消息队列的两种模式点对点模式发布/订阅模式Kafka基础架构Kafka快速入门安装部署集群规划集群部署集群启停脚本Kafka命令行操作Kafka基础架构主题命令行操作生产者命令行操作消费者命令行操作kafka可视化工具Kafka…...

(三)随处可见的LED广告屏是怎么工作的呢?接入GUI

续上文&#xff0c;本篇我们将尝试接入一个GUI来控制点阵屏。在前两篇中&#xff0c;我们相继介绍了点阵屏的控制原理&#xff0c;以及如何让点阵屏按照我们所想的进行显示。本篇将在此基础上接入一个GUI&#xff0c;使点阵屏的控制更加优雅。限于阅读体验和展示效果&#xff0…...

线程池简介

线程池 线程池&#xff08;英语&#xff1a;thread pool&#xff09;&#xff1a;一种线程使用模式。线程过多会带来调度开销&#xff0c;进而影响缓存局部性和整体性能。而线程池维护着多个线程&#xff0c;等待着监督管理者分配可并发执行的任务。这避免了在处理短时间任务时…...

大数据面试题集锦-Hadoop面试题(四)-YARN

你准备好面试了吗?这里有一些面试中可能会问到的问题以及相对应的答案。如果你需要更多的面试经验和面试题&#xff0c;关注一下"张飞的猪大数据分享"吧&#xff0c;公众号会不定时的分享相关的知识和资料。 文章目录1、为什么会产生 yarn,它解决了什么问题&#xf…...

Python---time模块

专栏&#xff1a;python 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;Python在学&#xff0c;希望能够得到各位的支持&#xff01;&#xff01;&#xff01; time模块前言时间戳time.time()将时间戳转换成字符串time.ctime()将时间戳转换为元组time.localtime(时间戳)将元…...

坚鹏:学习贯彻二十大精神 解码共同富裕之道(面向银行)

学习贯彻二十大精神 解码共同富裕之道课程背景&#xff1a; 很多银行从业人员存在以下问题&#xff1a;不知道如何准确解读二十大精神&#xff1f;不清楚共同富裕相关政策要求&#xff1f;不知道如何有效推动共同富裕&#xff1f; 课程特色&#xff1a;有实战案例有…...

python查看程序的cpu和内存资源占用情况

1.获取线程消耗的内存 :线程内存使用的概念没有明确定义。线程共享它们的内存。唯一真正的线程本地内存是它的调用堆栈&#xff0c;除非您认真地递归地做一些事情&#xff0c;否则这不是有趣的部分。 2.获取进程消耗的内存 3.获取程序消耗的内存 mprof run endpoint.py 4.查看…...

番外10:使用ADS对射频功率放大器进行非线性测试2(使用带宽20MHz的64QAM信号进行ACLR、EVM、CCDF测试)

番外10&#xff1a;使用ADS对射频功率放大器进行非线性测试2&#xff08;使用带宽20MHz的64QAM信号进行ACLR、EVM、CCDF测试&#xff09; 1、基本理论 功率放大器的非线性性能十分重要&#xff0c;特别是对于当前广泛使用的移动设备。由于其各种复杂的信号调制&#xff0c;功…...

Ubuntu搭建maven私服

1.安装JDK8 已经是JDK8的需要配置环境变量&#xff0c;如果是更高版本的JDK则需要修改nexus配置文件 2.下载nexus安装包 百度网盘下载&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1DfKqql8tZNQXEBxAEH7UyA 提取码&#xff1a;hx4p安装到有磁盘的目录如下所示&…...

【JavaWeb】Servlet基础

文章目录1.Tomcat服务器安装注意事项2.编写WebApp3.BS系统角色和协议4.模拟Servlet4.1模拟sun公司4.2模拟Tomcat服务器4.3模拟WebApp开发者5.开发一个带有Servlet的WebApp5.1创建一个名为crm的项目5.2 在项目中创建一个名为WEB-INF的文件&#xff08;必须&#xff09;5.3在WEB-…...

pinia + pinia-plugin-persistedstate + 组合式API 写法,持久化失效问题

持久化失效卡了一天的问题安装使用就不多说了&#xff0c;主要是针对持久化失效的几个问题说明和解决方法首先是组合式写法&#xff0c;配置持久化export const useUserStore defineStore(user, () > {},{persist: true} )defineStore 第三个参数&#xff0c;具体可以看 p…...

ptrace 调式详解

在程序出现bug的时候&#xff0c;最好的解决办法就是通过 GDB 调试程序&#xff0c;然后找到程序出现问题的地方。比如程序出现 段错误&#xff08;内存地址不合法&#xff09;时&#xff0c;就可以通过 GDB 找到程序哪里访问了不合法的内存地址而导致的。本文不是介绍GDB不是使…...

【AI绘画】绝美春天插画,人人都是插画师

春天&#xff0c;自然界重新苏醒&#xff0c;生机勃勃&#xff0c;百花争艳&#xff0c;万籁俱寂。一切都被新的生命活力所染上。春风拂面&#xff0c;一股清新的空气流过&#xff0c;仿佛带着一种神秘的力量&#xff0c;让人心旷神怡&#xff0c;心情舒畅、轻松愉悦。 突然&a…...

LangChain 1.0 中间件实战:5个钩子函数让你的Agent像专业工程师一样思考

LangChain 1.0中间件深度实践&#xff1a;5个钩子函数打造工程级Agent思维 当我们在2023年首次接触LangChain时&#xff0c;它还是一个以Chain为核心的实验性框架。如今&#xff0c;LangChain 1.0的发布标志着AI Agent开发正式进入生产就绪阶段。本文将带您深入探索其最具革命性…...

别再写死代码了!用MCP Tool模块5分钟搞定AI与数据库的安全对话

别再写死代码了&#xff01;用MCP Tool模块5分钟搞定AI与数据库的安全对话 当AI模型需要与数据库交互时&#xff0c;开发者常面临两难选择&#xff1a;要么直接暴露数据库连接信息&#xff0c;要么编写大量胶水代码。这两种方案都存在明显缺陷——前者带来安全隐患&#xff0c;…...

3分钟掌握的网盘密码解析黑科技:让提取码自动获取效率提升10倍

3分钟掌握的网盘密码解析黑科技&#xff1a;让提取码自动获取效率提升10倍 【免费下载链接】baidupankey 项目地址: https://gitcode.com/gh_mirrors/ba/baidupankey 你是否曾经因为寻找百度网盘分享链接的提取码而浪费大量时间&#xff1f;传统方式下&#xff0c;用户…...

从‘腐蚀液’到‘设计美学’:PCB布线‘禁止直角’这条规则是怎么流行起来的?

从工艺限制到设计美学&#xff1a;PCB布线"禁止直角"规则的历史演变 在电子工程领域&#xff0c;PCB布线中"禁止直角"的规则几乎成为了一种行业圣经。从大学实验室到商业设计部门&#xff0c;新手工程师们总是被反复告诫要避免在布线中使用90度转角。但有趣…...

厦门选117E还是120E?手把手教你为你的城市选择正确的高斯克吕格投影坐标系

厦门GIS项目实战&#xff1a;如何精准选择高斯克吕格投影坐标系 第一次在ArcGIS里看到上百个坐标系选项时&#xff0c;我的鼠标指针在列表上方徘徊了整整十五分钟——就像站在自动售货机前不知道按哪个按钮的新手。特别是当项目 deadline 临近&#xff0c;而厦门市规划局的Shap…...

57:L构建紫队协同:蓝队的协同防御

作者&#xff1a; HOS(安全风信子) 日期&#xff1a; 2026-03-07 主要来源平台&#xff1a; GitHub 摘要&#xff1a; 传统的红队和蓝队分离模式存在沟通障碍&#xff0c;导致防御效率低下。L构建了一套紫队协同系统&#xff0c;通过AI驱动的团队协作、知识共享和防御优化&…...

一键部署后的第一步:LiuJuan20260223Zimage API调用详解与调试

一键部署后的第一步&#xff1a;LiuJuan20260223Zimage API调用详解与调试 刚在星图GPU平台上一键部署好LiuJuan20260223Zimage镜像&#xff0c;看着运行状态显示“正常”&#xff0c;是不是感觉离用上强大的AI能力只差临门一脚了&#xff1f;别急&#xff0c;这最后一步——学…...

卷积计算常见误区解析:为什么你的结果和理论值对不上?

卷积计算常见误区解析&#xff1a;为什么你的结果和理论值对不上&#xff1f; 在图像处理和深度学习领域&#xff0c;卷积操作是基础中的基础。但令人惊讶的是&#xff0c;即使是经验丰富的开发者&#xff0c;在实际编码时也常常遇到计算结果与预期不符的情况。这就像做菜时严格…...

全能型 AI论文工具排行榜(2026 最新实测)

基于功能全面性、学术适配性、用户反馈质量以及操作便捷性&#xff0c;本文对当前主流AI论文写作工具进行了系统测评&#xff0c;按综合使用价值从高到低进行排序&#xff0c;并详细解析各工具的核心优势与适用领域。&#x1f3c6; 第一梯队&#xff1a;全流程学术解决方案&…...

告别校园网登录页!实测用UDP 53端口“曲线救国”上网的几种姿势与风险提示

校园网络优化&#xff1a;提升连接效率的合法实践指南 校园网络作为师生日常学习研究的重要基础设施&#xff0c;其稳定性和访问效率直接影响教学科研质量。许多用户在使用过程中会遇到认证页面频繁弹出、连接不稳定等问题&#xff0c;这通常与网络架构设计和流量管理策略有关。…...