题解采用了递归方法来搜索二叉搜索树(BST)。首先检查当前节点是否为空,若为空,则返回 null。接下来,比较当前节点的值与目标值。如果当前节点的值等于目标值,则返回当前节点,这意味着找到了目标节点,并将以此节点为根的子树作为结果返回。如果目标值小于当前节点的值,递归搜索当前节点的左子树;如果目标值大于当前节点的值,则递归搜索右子树。这个过程一直进行,直到找到目标值或者遍历完树(遇到空节点)。
时间复杂度: O(h),其中 h 是树的高度,最差情况下为 O(n),最好情况下为 O(log n)
空间复杂度: O(h),其中 h 是树的高度,最差情况下为 O(n),最好情况下为 O(log n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if root is None: # 检查当前节点是否为空
return None # 空节点,返回 None
if root.val == val: # 检查当前节点的值是否等于目标值
return root # 相等,返回当前节点作为子树的根
if root.val > val: # 如果当前节点值大于目标值
return self.searchBST(root.left, val) # 递归搜索左子树
if root.val < val: # 如果当前节点值小于目标值
return self.searchBST(root.right, val) # 递归搜索右子树