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 左小右大的特性，可以避免搜索整棵二叉树去寻找元素，从而提升效率。

1. 终止条件：

   • 如果当前节点为空，说明未找到目标值，返回 null。
   • 如果当前节点值等于目标值 val，直接返回该节点。

2. 递归查找：

   • 如果目标值 val 小于当前节点值，递归查找左子树。
   • 如果目标值 val 大于当前节点值，递归查找右子树。

3. 返回结果：递归返回目标节点或 null。

复杂度分析

• 时间复杂度：平均情况 O(log n)，每次递归会进入树的一半节点；最坏情况为 O(n)，树退化为链表。
• 空间复杂度：平均情况 O(log n)，最坏情况O(n)。

代码

/**
 * @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+	🟠	🀄️ 🔗