E-700. Search in a Binary Search Tree

Loading...LeetCode

'''
Time: O(H)
Space: O(H)
'''
# 0 写法1
class Solution:
    def __init__(self):
        self.ans=None
    
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return None
        if val < root.val:
            self.searchBST(root.left, val)
        if val == root.val:
            self.ans=root
        if root.val < val:
            self.searchBST(root.right,val)
        return self.ans

# 1 写法2
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        def ldr(root, ans): # <--注意, 如果是写这种传值的递归函数, 最后一定要返回一个值
            if not root:
                return None
            if val < root.val:
                ans = ldr(root.left, ans)
            if val == root.val:
                return root
            if val > root.val:
                ans = ldr(root.right, ans)
            return ans
                
        ans = ldr(root, None)
        return ans