700. 二叉搜索树中的搜索

🟢   🔖  树 二叉搜索树 二叉树  🔗 力扣 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);
};

相关题目

题号	标题	题解	标签	难度
270	最接近的二叉搜索树值 🔒		树 深度优先搜索 二叉搜索树 2+
701	二叉搜索树中的插入操作	[✓]	树 二叉搜索树 二叉树
2476	二叉搜索树最近节点查询		树 深度优先搜索 二叉搜索树 3+