原文链接: https://leetcode-cn.com/problems/search-in-a-binary-search-tree

英文原文

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

 

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= 107
• root is a binary search tree.
• 1 <= val <= 107

中文题目

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

例如，

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2

你应该返回如下子树:

      2     
     / \   
    1   3

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

通过代码

高赞题解

递归

根据题意，进行「递归」搜索即可。

代码：

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

• 时间复杂度：$O(n)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

迭代

同理，可以使用「迭代」进行搜索。

代码：

[]
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null && root.val != val) {
            root = root.val < val ? root.right : root.left;
        }
        return root;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

其他「树的搜索」相关内容

题太简单？不如来学习热乎的 图论搜索专题：双向 BFS 模板题

或是加练如下「树的搜索」相关内容 🍭🍭🍭

题目	题解	难度	推荐指数
74. 搜索二维矩阵	LeetCode 题解链接	中等	🤩🤩🤩🤩
173. 二叉搜索树迭代器	LeetCode 题解链接	中等	🤩🤩🤩🤩
331. 验证二叉树的前序序列化	LeetCode 题解链接	中等	🤩🤩🤩
671. 二叉树中第二小的节点	LeetCode 题解链接	简单	🤩🤩
700. 二叉搜索树中的搜索	LeetCode 题解链接	简单	🤩🤩🤩🤩
778. 水位上升的泳池中游泳	LeetCode 题解链接	困难	🤩🤩🤩
783. 二叉搜索树节点最小距离	LeetCode 题解链接	简单	🤩🤩🤩
872. 叶子相似的树	LeetCode 题解链接	简单	🤩🤩🤩
897. 递增顺序搜索树	LeetCode 题解链接	简单	🤩🤩🤩🤩
938. 二叉搜索树的范围和	LeetCode 题解链接	简单	🤩🤩🤩
993. 二叉树的堂兄弟节点	LeetCode 题解链接	简单	🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
120736	156020	77.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最接近的二叉搜索树值	简单
二叉搜索树中的插入操作	中等