leetcode
leetcode 651 ~ 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, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

代码结果

运行时间: 68 ms, 内存: 17.1 MB

// 思路：
// 使用 Java 8 的 Optional 和 Stream 来查找 BST 中的节点。
// 首先创建一个方法，通过 Optional.ofNullable(root) 开始，
// 递归地将左或右子树的节点包装为 Optional，直到找到匹配的节点。
 
import java.util.Optional;
 
public class Solution {
    public Optional<TreeNode> searchBST(TreeNode root, int val) {
        return Optional.ofNullable(root)
                .flatMap(node -> val < node.val ? searchBST(node.left, val)
                        : val > node.val ? searchBST(node.right, val)
                        : Optional.of(node));
    }
}

解释

方法:

题解采用了递归方法来搜索二叉搜索树（BST）。首先检查当前节点是否为空，若为空，则返回 null。接下来，比较当前节点的值与目标值。如果当前节点的值等于目标值，则返回当前节点，这意味着找到了目标节点，并将以此节点为根的子树作为结果返回。如果目标值小于当前节点的值，递归搜索当前节点的左子树；如果目标值大于当前节点的值，则递归搜索右子树。这个过程一直进行，直到找到目标值或者遍历完树（遇到空节点）。

时间复杂度:

O(h)，其中 h 是树的高度，最差情况下为 O(n)，最好情况下为 O(log n)

空间复杂度:

O(h)，其中 h 是树的高度，最差情况下为 O(n)，最好情况下为 O(log n)

代码细节讲解

🦆
在递归函数中，如果已经确定当前节点的值不等于目标值，为什么接下来只选择搜索左子树或右子树中的一个？
▷
因为在二叉搜索树（BST）中，所有左子节点的值都小于其父节点的值，而所有右子节点的值都大于其父节点的值。这种结构使得搜索可以高效进行：如果目标值小于当前节点的值，那么目标值必然不会出现在当前节点的右子树中，因此只需要搜索左子树；同样地，如果目标值大于当前节点的值，则目标值不会出现在左子树中，因此只需要搜索右子树。这样的逻辑确保了搜索过程是高效的，不需要检查不相关的部分。
🦆
递归搜索中如果目标值不存在于树中，这种情况是如何被处理的，具体在代码中是通过什么逻辑来实现返回`null`的？
▷
如果目标值不存在于树中，搜索过程最终会达到树的叶节点的子节点（即空节点）。在代码中，每次递归调用首先检查当前节点是否为空（`if root is None`），如果是空的，说明已经到达了树的边界但未找到目标值，因此返回`null`。这种方式自然地处理了目标值不存在的情况，因为搜索路径最终总会遇到空节点。
🦆
在递归过程中，如果二叉树的每个节点都存了额外的信息（如子树大小），这是否可能帮助提高搜索效率？如果可以，应该如何修改现有的搜索算法？
▷
在普通的BST搜索过程中，存储额外信息如子树的大小不会直接提高搜索效率，因为搜索依赖于比较节点值。但是，这类信息可以在其他操作中提供优势，如在平衡二叉树（如AVL树或红黑树）中维护平衡或在选择操作（找第k小的元素）时。如果要利用子树大小信息来提高搜索效率，可能需要考虑不同的数据结构或算法，如在维护平衡的同时进行搜索，通过控制树的高度来间接提高搜索效率。
🦆
代码中对于`root`为空的判断是在每次递归调用时都进行，这种方式是否最优，还是有其他更高效的处理空节点的方法？
▷
在递归搜索中，对于`root`为空的判断是必要的，它属于递归停止的基本条件之一。没有更高效的方法来省略这个检查，因为每次递归都可能达到树的边界。此外，这个检查也是确保程序不会因尝试访问空对象的属性而崩溃的关键。因此，这种方式是最优的，确保了程序的健壮性和正确性。

相关问题

最接近的二叉搜索树值

最接近的二叉搜索树值

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

 

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

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

 

提示：

  • 树中的节点数将在 [0, 104]的范围内。
  • -108 <= Node.val <= 108
  • 所有值 Node.val 是 独一无二 的。
  • -108 <= val <= 108
  • 保证 val 在原始BST中不存在。
宝石与石头二叉搜索树中的插入操作