【算法与数据结构】700、LeetCode二叉搜索树中的搜索

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:二叉搜索树的性质:左节点键值 < 中间节点键值 < 右节点键值。那么我们根据此性质,对比目标值和中间节点,如果val值较小在左边子树进行搜索,否则在右边子树进行搜索。程序采用递归实现。
  程序如下

class Solution {
public:// 递归法// 1、输入参数TreeNode* searchBST(TreeNode* root, int val) { // 2.终止条件if (root == NULL || root->val == val) return root;   // 找到目标值,标志位变为1,返回目标节点// 3.单层递归逻辑:对比根节点和val       if (root->val > val) return searchBST(root->left, val); // val较小,在左边子树            if (root->val < val) return searchBST(root->right, val); // val较大,在右边子树// 1.返回值return NULL;}
};

复杂度分析:

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

三、完整代码

# include <iostream>
# include <vector>
# include <string>
# include <queue>
# include <stack>
using namespace std;// 树节点定义
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:// 递归法// 1、输入参数TreeNode* searchBST(TreeNode* root, int val) { // 2.终止条件if (root == NULL || root->val == val) return root;   // 找到目标值,标志位变为1,返回目标节点// 3.单层递归逻辑:对比根节点和val       if (root->val > val) return searchBST(root->left, val); // val较小,在左边子树            if (root->val < val) return searchBST(root->right, val); // val较大,在右边子树// 1.返回值return NULL;}
};// 前序遍历迭代法创建二叉树,每次迭代将容器首元素弹出(弹出代码还可以再优化)
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (!t.size() || t[0] == "NULL") return;    // 退出条件else {node = new TreeNode(stoi(t[0].c_str()));    // 中if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left);              // 左}if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right);             // 右}}
}template<typename T>
void my_print(T& v, const string msg)
{cout << msg << endl;for (class T::iterator it = v.begin(); it != v.end(); it++) {cout << *it << ' ';}cout << endl;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();  // size必须固定, que.size()是不断变化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}int main()
{vector<string> t1 = { "4", "2", "1", "NULL", "NULL", "3", "NULL", "NULL", "7", "NULL", "NULL" };   // 前序遍历my_print(t1, "目标树");TreeNode* root1 = new TreeNode();Tree_Generator(t1, root1);vector<vector<int>> tree1 = levelOrder(root1);my_print2<vector<vector<int>>, vector<int>>(tree1, "目标树:");Solution s;int val = 2;TreeNode* root = s.searchBST(root1, val);vector<vector<int>> tree = levelOrder(root);my_print2<vector<vector<int>>, vector<int>>(tree, "目标树:");system("pause");return 0;
}

end

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/121591.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

seata1.4.2版本配置总结

文章目录 环境准备&#xff1a;seata-server配置registry.conf创建数据库表 nacos配置client配置seata_orderseata_storageseata_account 注意点 创建项目seata-order-service2001pom.xml文件application.yml 实体类CommonResultOrder DaoOrderDaoOrderMapper.xml config配置类…

文件上传漏洞全面渗透姿势

0x00 文件上传场景 (本文档只做技术交流) 文件上传的场景真的随处可见&#xff0c;不加防范小心&#xff0c;容易造成漏洞&#xff0c;造成信息泄露&#xff0c;甚至更为严重的灾难。 比如某博客网站评论编辑模块&#xff0c;右上角就有支持上传图片的功能&#xff0c;提交带…

指令系统(408)

一、拓展操作码指令格式 【2017 统考】某计算机按字节编址&#xff0c;指令字长固定且只有两种指令格式&#xff0c;其中三地址指令29条、二地址指令107条&#xff0c;每个地址字段6位&#xff0c;则指令字长至少应该是&#xff08; A&#xff09; A、24位 B、26位 …

Springboot + Sqlite实战(离线部署成功)

最近有个需求&#xff0c;是手机软件离线使用&#xff0c; 用的springboot mybatis-plus mysql&#xff0c;无法实现&#xff0c;于是考虑使用内嵌式轻量级的数据库SQLlite 引入依赖 <dependency><groupId>org.xerial</groupId><artifactId>sqlite-…

清理docker镜像方法

首先stop ps -a里的容器&#xff0c;然后rm容器&#xff0c;最后再rmi镜像 先停止容器 rm容器 docker rmi 镜像 删除后可以发现已经不存在

论文复现--VideoTo3dPoseAndBvh(视频转BVH和3D关键点开源项目)

分类&#xff1a;动作捕捉 github地址&#xff1a;https://github.com/HW140701/VideoTo3dPoseAndBvh 所需环境&#xff1a; Windows10&#xff0c;CUDA11.6&#xff0c;conda 4.13.0&#xff1b; 目录 环境搭建conda list配置内容演示生成文件说明 环境搭建 # 创建环境 conda…

uniapp 配置并使用 VueX

Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态&#xff0c;并以相应的规则保证状态以一种可预测的方式发生变化。 uni-app 内置了 VueX 1、创建需要的文件 右键点击 根目录【我的是 uni-shop】&#xff0c;然后新建 目录&a…

网络安全-IP地址信息收集

本文为作者学习文章&#xff0c;按作者习惯写成&#xff0c;如有错误或需要追加内容请留言&#xff08;不喜勿喷&#xff09; 本文为追加文章&#xff0c;后期慢慢追加 IP反查域名 http://stool.chinaz.com/same https://tools.ipip.net/ipdomain.php 如果渗透目标为虚拟主机…

【力扣每日一题】2023.9.4 序列化和反序列化二叉搜索树

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们一棵搜索二叉树&#xff0c;要我们将这棵二叉树转变为字符串&#xff0c;同时我们需要根据字符串再变回二叉树&#xff0c;具体…

基于单片机的万年历温度无线传输控制系统系统

一、系统方案 本设计采用DS1302采集年月日时分秒&#xff0c;DS18B20采集温度值&#xff0c;按键设置温度报警上下限&#xff0c;实际测量温度低于下限或高于上限&#xff0c;蜂鸣器报警&#xff0c;同时将测量温度上传到蓝牙助手。 二、硬件设计 原理图如下&#xff1a; 三…

基于Matlab实现频谱分析(附上源码+数据集)

Matlab是一个功能强大的数值计算和科学计算软件&#xff0c;可以用于频谱分析。频谱分析是一种信号处理技术&#xff0c;用于将时域信号转换为频域信号&#xff0c;以便更好地理解信号的频率特性。本文将介绍使用Matlab实现频谱分析的方法。 文章目录 部分源码完整源码数据集下…

Mysql高阶语句(二)

一、设置别名&#xff08;alias ——>as&#xff09; 在 MySQL 查询时&#xff0c;当表的名字比较长或者表内某些字段比较长时&#xff0c;为了方便书写或者 多次使用相同的表&#xff0c;可以给字段列或表设置别名。使用的时候直接使用别名&#xff0c;简洁明了&#xff0…

【微服务部署】三、Jenkins+Maven插件Jib一键打包部署SpringBoot应用Docker镜像步骤详解

前面我们介绍了K8SDockerMaven插件打包部署SpringCloud微服务项目&#xff0c;在实际应用过程中&#xff0c;很多项目没有用到K8S和微服务&#xff0c;但是用到了Docker和SpringBoot&#xff0c;所以&#xff0c;我们这边介绍&#xff0c;如果使用Jenkinsjib-maven-plugin插件打…

无涯教程-Android - List fragments函数

框架的ListFragment的静态库支持版本&#xff0c;用于编写在Android 3.0之前的平台上运行的应用程序&#xff0c;在Android 3.0或更高版本上运行时,仍使用此实现。 List fragment 的基本实现是用于创建fragment中的项目列表 List in Fragments 示例 本示例将向您说明如何基于…

LSM树详解

LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象&#xff0c;事实上&#xff0c;LSM树并不像B树、红黑树一样是一颗严格的树状数据结构&#xff0c;它其实是一种存储结构&#xff0c;目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。 LSM树的核…

Redis-Cluster集群操作--添加节点、删除节点

一、环境部署 部署好Redis-Cluster集群&#xff0c;参考上个本人的博客&#xff1a;Redis-Cluster集群的部署&#xff08;详细步骤&#xff09;_是胡也是福的博客-CSDN博客 新准备一台机器&#xff0c;修改主机名&#xff0c;关闭防火墙和selinux&#xff0c;参考&#xff1a…

Jupyter Notebook 好用在哪?

Jupyter Notebook 是一个 Web 应用程序&#xff0c;便于创建和共享文学化程序文档&#xff0c;支持实时代码、数学方程、可视化和 Markdown&#xff0c;其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前&#xff0c;数据挖掘领域中最热门的比赛 Kaggle 里的资…

EI、Scopus双检索| 2023年第四届自动化、机械与设计工程国际会议

会议简介 Brief Introduction 2023年第四届自动化、机械与设计工程国际会议&#xff08;SAMDE 2023&#xff09; 会议时间&#xff1a;2023年12月8 -10日 召开地点&#xff1a;中国南京 大会官网&#xff1a;www.samde.org 机械设计制造及其自动化学科在国民经济中处于极其重要…

数学建模--最短路径算法的Python实现

目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 #最短路径算法 #针对有向图的最短路径问题,我们有很多的算法能解决. """ 目前主流算法如下所示: Dijkstra算法:Dijkstra算法是一种单源最短路径算法,用于计算从起点到其它所有节点的最短…

java八股文面试[多线程]——线程间通信方式

多个线程在并发执行的时候&#xff0c;他们在CPU中是随机切换执行的&#xff0c;这个时候我们想多个线程一起来完成一件任务&#xff0c;这个时候我们就需要线程之间的通信了&#xff0c;多个线程一起来完成一个任务&#xff0c;线程通信一般有4种方式&#xff1a; 通过 volat…