700. Search in a Binary Search Tree
700. 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:
![](https://assets.leetcode.com/uploads/2021/01/12/tree1.jpg)
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
Example 2:
![](https://assets.leetcode.com/uploads/2021/01/12/tree2.jpg)
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 <= 10^7
root
is a binary search tree.1 <= val <= 10^7
题目大意
给定二叉搜索树(BST)的根节点和一个值,你需要在 BST 中找到节点值等于给定值的节点,返回以该节点为根的子树,如果节点不存在,则返回 NULL
。
解题思路
利用 BST 左小右大的特性,可以避免搜索整棵二叉树去寻找元素,从而提升效率。
代码
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var searchBST = function (root, val) {
if (!root || val == root.val) return root;
if (val < root.val) return searchBST(root.left, val);
return searchBST(root.right, val);
};
相关题目
相关题目
- [🔒 Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value)
- [701. 二叉搜索树中的插入操作](./0701.md)
- [2476. 二叉搜索树最近节点查询](https://leetcode.com/problems/closest-nodes-queries-in-a-binary-search-tree)