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)