当前位置: 首页 > 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…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...