【LeetCode】二叉搜索树中的搜索Java题解 题目描述

发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
makefile复制代码例如

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

  • 今天的算法每日一题是二叉搜索树查找问题。什么是二叉搜索树呢？
  • 二叉搜索树（Binary Search Tree 或者是一棵空树，或者是具有下列性质的二叉树：
  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树。
  • 利用二叉搜索树以上的性质，我们就可以快速查找题目节点子树。实现代码如下：

通过代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
java复制代码/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        } else if (root.val > val)  {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

image.png

总结

  • 递归算法的时间复杂度是O(log n),空间复杂度是O(log n)
  • 二叉搜索树是一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。我们要掌握好这种数据结构。
  • 坚持算法每日一题，加油！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%