24_二叉搜索树中的搜索

简介: 24_二叉搜索树中的搜索

700. 二叉搜索树中的搜索

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

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

示例 1:

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

示例 2:

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

【思路】

二叉搜索树是一个有序树:

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

递归法

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

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

TreeNode searchBST(TreeNode root, int val);

2、确定终止条件

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

if (root == null || root.val == val)  return root;

3、确定单层递归的逻辑

TreeNode result = null;
if (root.val < val) result = searchBST(root.right, val);
if (root.val > val) rersult = searchBST(root.left, val);
return result;

整体代码如下:

class Solution {
    // 递归,利用二叉搜索树特点,优化
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

迭代法

一提到二叉树遍历的迭代法,可能立刻想起使用栈来模拟深度遍历,使用队列来模拟广度遍历。

对于二叉搜索树是不一样的,因为二叉搜索树的特殊性,也就是节点的有序性,可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树,递归过程中还有回溯的过程,例如走一个左方向的分支走到头了,那么要掉头,在走右分支。

而对于二叉搜索树,不需要回溯的过程,因为节点的有序性就帮我们确定了搜索的方向。例如要搜索元素为3的节点,我们不需要搜索其他节点,也不需要做回溯,查找的路径已经规划好了。

class Solution {
  TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val > val) root = root.left;
            else if (root.val < val) root = root.right;
            else return root;
        }
        return null;
    }
}
JAVA 复制 全屏

总结

本篇我们介绍了二叉搜索树的遍历方式,因为二叉搜索树的有序性,遍历的时候要比普通二叉树简单很多。

但是一些同学很容易忽略二叉搜索树的特性,所以写出遍历的代码就未必真的简单了。

所以针对二叉搜索树的题目,一样要利用其特性。

文中我依然给出递归和迭代两种方式,可以看出写法都非常简单,就是利用了二叉搜索树有序的特点。

相关文章
|
自然语言处理 安全 算法
23REPEAT方法:软工顶会ICSE ‘23 大模型在代码智能领域持续学习 代表性样本重放(选择信息丰富且多样化的示例) + 基于可塑权重巩固EWC的自适应参数正则化 【网安AIGC专题11.22】
23REPEAT方法:软工顶会ICSE ‘23 大模型在代码智能领域持续学习 代表性样本重放(选择信息丰富且多样化的示例) + 基于可塑权重巩固EWC的自适应参数正则化 【网安AIGC专题11.22】
817 0
23REPEAT方法:软工顶会ICSE ‘23 大模型在代码智能领域持续学习 代表性样本重放(选择信息丰富且多样化的示例) + 基于可塑权重巩固EWC的自适应参数正则化 【网安AIGC专题11.22】
|
存储 算法 数据可视化
数据分析入门系列教程-K-Means原理
数据分析入门系列教程-K-Means原理
数据分析入门系列教程-K-Means原理
|
7天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
8896 23
|
7天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2683 12
|
2天前
|
人工智能 安全 应用服务中间件
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
NGINX曝出两个高危漏洞(CVE-2026-123633和CVE-2026-123007),CVSS 9.2分,均属HTTP/2内存安全缺陷,无需认证即可远程执行代码。影响自2015年起的多个版本,静态站点亦受威胁。修复版本为开源版1.30.7/1.31.9。(239字)
1279 0
NGINX 爆出两处高危漏洞 可导致未经身份验证的远程代码执行
|
5天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
10天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
10天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
23天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
11065 59
|
3天前
|
人工智能 弹性计算 IDE
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
适合团队落地代码规范,每次提交自动生成评审报告,降低人工CR工作量。同时支持自定义技能脚本,接入团队内部SDK说明文档,让Codex生成符合团队编码规范的代码。Codex三大客户端覆盖本地开发、服务器远程编码、自动化流水线场景,搭配阿里云百炼的Token Plan、Coding Plan,能够低成本搭建稳定可控的AI编码助手。新手建议先从IDE插件入手,熟悉交互逻辑,再尝试CLI版本部署在阿里云ECS,实现云上项目远程编码、批量脚本处理。只要按照步骤完成环境准备、版本选型、密钥对接、项目初始化,就可以把Codex融入日常开发流程,大幅提升代码编写、问题排查、项目重构的效率。
935 0