跳至主要內容

0700. 二叉搜索树中的搜索

ITCharge大约 1 分钟

0700. 二叉搜索树中的搜索open in new window

  • 标签:树、二叉搜索树、二叉树
  • 难度:简单

题目链接

题目大意

描述:给定一个二叉搜索树和一个值 val

要求:在二叉搜索树中查找节点值等于 val 的节点,并返回该节点。

说明

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

示例

  • 示例 1:
img
img
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]
  • 示例 2:
输入:root = [4,2,7,1,3], val = 5
输出:[]

解题思路

思路 1:递归

  1. 从根节点 root 开始向下递归遍历。
    1. 如果 val 等于当前节点的值,即 val == root.val,则返回 root
    2. 如果 val 小于当前节点的值 ,即 val < root.val,则递归遍历左子树,继续查找;
    3. 如果 val 大于当前节点的值 ,即 val > root.val,则递归遍历右子树,继续查找。
  2. 如果遍历到最后也没有找到,则返回空节点。

思路 1:代码

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

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)。其中 nn 是二叉搜索树的节点数。
  • 空间复杂度O(n)O(n)