700. Search in a Binary Search Tree

🟢   🔖  树 二叉搜索树 二叉树  🔗 LeetCode

题目

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 <= 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
• 701. 二叉搜索树中的插入操作
• 2476. 二叉搜索树最近节点查询

- [🔒 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)