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

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

ZYNQ学习记录FPGA(二)Verilog语言

一、Verilog简介 1.1 HDL&#xff08;Hardware Description language&#xff09; 在解释HDL之前&#xff0c;先来了解一下数字系统设计的流程&#xff1a;逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端&#xff0c;在这个过程中就需要用到HDL&#xff0c;正文…...