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 复制 全屏

总结

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

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

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

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

相关文章
|
10月前
|
机器学习/深度学习 人工智能 自然语言处理
Sketch2Lineart:AI绘画工具,自动将手绘草图转换成清晰的线条画
Sketch2Lineart是一款基于人工智能的绘画工具,能够自动将手绘草图转换成清晰的线条画。该工具支持多种功能,如草图转线稿、自动描述生成、细节调整和风格定制等,适用于艺术创作、产品设计、教育培训等多个领域。
806 60
Sketch2Lineart:AI绘画工具,自动将手绘草图转换成清晰的线条画
|
机器学习/深度学习 数据采集 算法
数据分享|R语言机器学习预测案例合集:众筹平台、机票折扣、糖尿病患者、员工满意度
数据分享|R语言机器学习预测案例合集:众筹平台、机票折扣、糖尿病患者、员工满意度
|
数据库连接 数据库
Entity Framework Core 中的延迟加载与即时加载大揭秘!性能考量全知道,助你高效开发!
【8月更文挑战第31天】Entity Framework Core (EF Core) 是一款强大的对象关系映射(ORM)框架,支持延迟加载与即时加载两种方式。延迟加载即访问关联实体时再加载,适用于减少初始查询负载,但可能导致多次数据库查询;即时加载则在查询主实体时一并加载关联实体,减少数据库访问次数,但可能增加初始查询复杂度。选择加载方式需综合考虑查询复杂性、数据量及数据库连接管理等因素。
263 0
|
网络安全 Python
Python:获取ssl证书信息和到期时间
Python:获取ssl证书信息和到期时间
1238 0
使用react-vant上传图片遇到的问题
使用react-vant上传图片遇到的问题
|
搜索推荐 算法 数据库
正排索引 vs 倒排索引 - 搜索引擎具体原理
正排索引 vs 倒排索引 - 搜索引擎具体原理
758 4
|
算法 计算机视觉
图像处理之Lanczos采样放缩算法
图像处理之Lanczos采样放缩算法
482 0
|
存储 弹性计算 容灾
ECS快照问题之账户可以跨服务器/跨账号回滚吗
阿里云ECS用户可以创建的一个虚拟机实例或硬盘的数据备份,用于数据恢复和克隆新实例;本合集将指导用户如何有效地创建和管理ECS快照,以及解决快照过程中可能遇到的问题,确保数据的安全性和可靠性。
|
存储 前端开发 Java
第十一章 Spring Cloud Alibaba nacos配置中心
第十一章 Spring Cloud Alibaba nacos配置中心
361 0
|
Shell Docker 容器
mac终端命令补全设置(docker 命令补全)
mac终端命令补全设置(docker 命令补全)
371 0