Easy

题目描述

给定一个二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点，并返回以该节点为根的子树。如果节点不存在，则返回 null。

示例 1：

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2：

输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

  • 数中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 10^7
  • root 是二叉搜索树
  • 1 <= val <= 10^7

解题思路

这是一道利用二叉搜索树（BST）性质的经典题目。BST的核心性质是：对于任意节点，其左子树所有节点的值都小于该节点值，右子树所有节点的值都大于该节点值。

解题思路：

我们可以利用BST的性质进行高效搜索：

  1. 从根节点开始比较当前节点值与目标值
  2. 如果当前节点值等于目标值，直接返回当前节点
  3. 如果目标值小于当前节点值，说明目标节点在左子树中，递归搜索左子树
  4. 如果目标值大于当前节点值，说明目标节点在右子树中，递归搜索右子树
  5. 如果遍历到空节点，说明目标值不存在，返回null

两种实现方式：

  • 递归解法：代码简洁，思路清晰
  • 迭代解法：空间复杂度更优，避免递归调用栈

由于BST的特殊性质，我们无需遍历所有节点，每次都能排除一半的搜索空间，实现O(log n)的时间复杂度。

代码实现

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root || root->val == val) {
            return root;
        }
        
        if (val < root->val) {
            return searchBST(root->left, val);
        } else {
            return searchBST(root->right, val);
        }
    }
};

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        
        if val < root.val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

public class Solution {
    public TreeNode SearchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        
        if (val < root.val) {
            return SearchBST(root.left, val);
        } else {
            return SearchBST(root.right, val);
        }
    }
}

var searchBST = function(root, val) {
    if (!root) return null;
    
    if (root.val === val) {
        return root;
    } else if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归解法迭代解法
时间复杂度O(log n) - 平衡树，O(n) - 最坏情况O(log n) - 平衡树，O(n) - 最坏情况
空间复杂度O(log n) - 递归栈深度O(1) - 仅使用常数空间

注：在平衡的BST中时间复杂度为O(log n)，但在极端不平衡的情况下（如链式结构）时间复杂度会退化为O(n)。

相关题目