专栏首页小浩算法第38期:BST 的搜索(小白必看)

第38期:BST 的搜索(小白必看)

在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习! 下面我们仍然通过例题进行讲解。

01、题目分析

第700题:二叉搜索树中的搜索

给定二叉搜索树(BST)的根节点和一个值。你需要在 BST 中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL 。

示例:

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3
    
和值: 2

你应该返回如下子树:

      2     
     / \   
    1   3

在上述示例中,如果要找的值是 5 ,但因为没有节点值为 5 ,我们应该返回 NULL 。

本题为必须掌握! 需要非常熟悉 为后续题目打基础!

02、复习巩固

先复习一下,二叉搜索树(BST)的特性:

  • 若它的左子树不为空,则所有左子树上的值均小于其根节点的值
  • 若它的右子树不为空,则所有右子树上的值均大于其根节点得值
  • 它的左右子树也分别为二叉搜索树

如下图就是一棵典型的BST:

03、图解分析

假设目标值为 val,根据BST的特性,我们可以很容易想到查找过程

  • 如果val小于当前结点的值,转向其左子树继续搜索;
  • 如果val大于当前结点的值,转向其右子树继续搜索;
  • 如果已找到,则返回当前结点。

很简单,不是吗?

04、代码示例

给出递归和迭代两种解法:

//递归 
public TreeNode searchBST(TreeNode root, int val) { 
    if (root == null) 
        return null; 
    if (root.val > val) { 
        return searchBST(root.left, val);    
    } else if (root.val < val) {
        return searchBST(root.right, val);
    } else {
        return root;
    }
}
//迭代
public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            } else if (root.val > val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return null;
 }

递归与迭代的区别 递归:重复调用函数自身实现循环称为递归; 迭代:利用变量的原值推出新值称为迭代,或者说迭代是函数内某段代码实现循环;

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 第39期:小白一看就会的 BST 删除!

    在两节中,我们了解了BST(二叉搜索树)的概念,并且知道了如何在BST中查找一个元素。那我们又如何在BST中去删除一个元素呢?我们将通过本节的例题进行学习! 下...

    程序员小浩
  • hihocoder-平衡树·SBT

     http://hihocoder.com/problemset/problem/1337 #1337 : 平衡树·SBT 时间限制:10000ms 单点时限:...

    Gxjun
  • 第36期:二叉树的遍历(小白必看)

    BFS,广度/宽度优先。其实就是从上到下,先把每一层遍历完之后再遍历一下一层。假如我们的树如下:

    程序员小浩
  • 基本算法|图解各种树(二)

    01 — 二叉搜索树 基本算法|图解各种树(一) 二叉搜索树,又称为二叉排序树,简写为 BST,它与线性表,链表,二叉树间的关系,二维链表近似是二叉树,BST继...

    double
  • 漫画:二叉树系列 第四讲(BST的查找)

    在上一节中,我们学习了二叉搜索树。那我们如何在二叉搜索树中查找一个元素呢?和普通的二叉树又有何不同?我们将在本节内容中进行学习!

    程序员小浩
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • LeetCode 96,n个数构建BST的方法有多少种?

    今天是LeetCode专题第62篇文章,我们一起来聊聊LeetCode的96题,Unique Binary Search Trees(唯一的二叉搜索树)。

    TechFlow-承志
  • 整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

    没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是...

    Java程序猿阿谷
  • C++版 - 剑指offer 面试题24:二叉搜索树BST的后序遍历序列(的判断) 题解

    题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

    Enjoy233

扫码关注云+社区

领取腾讯云代金券