二叉树——700.二叉搜索树中的搜索

简介: 本专栏按照数组—链表—哈希—字符串—栈与队列—二叉树—回溯—贪心—动态规划—单调栈的顺序刷题,采用代码随想录所给的刷题顺序,一个正确的刷题顺序对算法学习是非常重要的,希望对大家有帮助

1 题目描述

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

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-in-a-binary-search-tree

2 题目示例

image.png

image.png

3 题目提示

数中节点数在 [1, 5000] 范围内
1 <= Node.val <= 10^7
root 是二叉搜索树
1 <= val <= 10^7

4 思路

方法一:递归
二叉搜索树满足如下性质:

  • 左子树所有节点的元素值均小于根的元素值;
  • 右子树所有节点的元素值均大于根的元素值。

据此可以得到如下算法:

  • 若root为空则返回空节点;
  • 若val = root.val,则返回root;
  • 若val < root.val,递归左子树;
  • 若val > root.val,递归右子树。

复杂度分析

  • 时间复杂度:O(N),其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要递归N次
  • 空间复杂度:O(N)。最坏情况下递归需要O(N)的栈空间。

方法二:迭代
我们将方法—的递归改成迭代写法:

  • 若root为空则跳出循环,并返回空节点;
  • 若val= root.val,则返回root;
  • 若val <root.val,将root置为root.left;
  • 若val > root.val,将root置为root.right。

复杂度分析

  • 时间复杂度:O(N),其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要迭代Ⅳ次
  • 空间复杂度:O(1)。没有使用额外的空间。

5 我的答案

递归:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

迭代:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (val == root.val) {
                return root;
            }
            root = val < root.val ? root.left : root.right;
        }
        return null;
    }
}
相关文章
|
6月前
|
算法
【递归搜索回溯专栏】专题二:二叉树中的深搜----二叉搜索树中第K小的元素
【递归搜索回溯专栏】专题二:二叉树中的深搜----二叉搜索树中第K小的元素
39 0
|
6月前
|
Java C++ Python
leetcode-700:二叉搜索树中的搜索
leetcode-700:二叉搜索树中的搜索
417 0
代码随想录Day16 LeetCode T654 最大二叉树 T617 合并二叉树 T700 二叉搜索树中的搜索
代码随想录Day16 LeetCode T654 最大二叉树 T617 合并二叉树 T700 二叉搜索树中的搜索
49 0
24_二叉搜索树中的搜索
24_二叉搜索树中的搜索
|
1月前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
16 0
|
存储 编译器 C语言
二叉树搜索
在之前的我们已经学过了普通二叉树,了解了基本的二叉树的结构和基本操作了,不过我们之前的二叉树结构都是使用C语言实现的,我们这次来介绍二叉树中更加复杂的树结构,C语言在实现这些结构已经有些吃力了,更适合我们使用C++来实现。
|
算法
代码随想录训练营day20| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树...
代码随想录训练营day20| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树...
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]
86 0
Leedcode二叉搜索树中的搜索[层序遍历+利用性质]
|
算法
LeetCode 第 1373 题:二叉搜索子树的最大键值和
在判断是否为 BST 的时候,可以使用后序遍历来记录 root 的左右子树是否为 BST 并且返回 root 树的最大和最小值,以及 root 的键值和。
93 0