Search In a Binary Search Tree

700. 二叉搜索树中的搜索

分析

递归查找：
- 如果当前节点为空，返回 null，表示未找到目标节点
- 如果当前节点的值等于目标值 val，返回该节点
- 如果当前节点的值大于 val，递归查找其左子树
- 如果当前节点的值小于 val，递归查找其右子树
返回结果：
- 如果找到目标节点，返回其为根的子树
- 如果未找到目标节点，返回 null

时间复杂度

最坏情况下为树的高度 O(h)，其中 h 是树的高度。对于平衡二叉搜索树，时间复杂度为 O(log n)

对于退化为链表的情况，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(h)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution
{
public:
    TreeNode* searchBST(TreeNode* root, int val)
    {
      // 基本情况：当前节点为空，返回 nullptr
      if (!root)
        return nullptr;

      // 当前节点的值大于目标值，递归查找左子树
      if (root->val > val)
        return searchBST(root->left, val);

      // 当前节点的值小于目标值，递归查找右子树
      if (root->val < val)
        return searchBST(root->right, val);

      // 找到目标节点，返回该节点
      return root;
    }
};