- 문제 링크: https://leetcode.com/problems/search-in-a-binary-search-tree/

 

이진 탐색트리(BST, Binary Search Tree)에서 주어진 값이 있는지 찾고, 있으면 해당 노드부터의 서브트리를 반환, 없으면 null 또는 None 등을 반환하는 문제입니다. 난이도는 Easy입니다

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if val == root.val:
            return root
        elif val < root.val and root.left:
            return self.searchBST(root.left, val)
        elif val > root.val and root.right:
            return self.searchBST(root.right, val)
        else:
            return None

어렵지 않죠. 루트(=현재노드)랑 비교해서 찾는 값이 작으면 왼쪽, 아니면 오른쪽을 찾아봅니다. 이때 왼쪽 자식이 있는지, 없는지 체크도 해줘야 합니다.

반응형

« 1 2 3 4 5 6 7 8 9 10 »