0700. 二叉搜索树中的搜索

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

  • 标签:树
  • 难度:简单

题目大意 #

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

解题思路 #

递归遍历。

  • 如果 val 等于当前节点的值,即 val == root.val,则返回 root;
  • 如果 val 小于当前节点的值 ,即 val < root.val,则递归遍历左子树,继续查找;
  • 如果 val 大于当前节点的值 ,即 val > root.val,则递归遍历右子树,继续查找。

若最终也没有找到,返回空节点。

代码 #

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)
本站总访问量  次  |  您是本站第  位访问者