0700. 二叉搜索树中的搜索

0700. 二叉搜索树中的搜索 #

  • 标签:树
  • 难度:简单

题目大意 #

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

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

说明

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

示例

img

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

img

1
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:代码 #

1
2
3
4
5
6
7
8
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)$。其中 $n$ 是二叉搜索树的节点数。
  • 空间复杂度:$O(n)$。
本站总访问量  次  |  您是本站第  位访问者