Leetcode: Search in a Binary Search Tree 파이썬 풀이

 

문제: Search in a Binary Search Tree
등급: Easy

내용: 이진 트리와 val가 주어지는데, 이진트리에서 val를 찾아야함.

<코드>

# 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):
        if not root:
            return None
        
        if root.val == val:
            return root
        
        return self.searchBST(root.left, val) or self.searchBST(root.right,val)
        
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """

오, 이게 되네...

 

<논리>

굉장히 간단한 코드이다. root가 없으면, None을 반환하고, root.val ==val일 경우, root을 반환한다. 

 

그리고, 계속 재귀 호출을 통해 breadth-first-search, 너비 우선 탐색을 통해 찾아준다. 계속 root가 node도 아니고, ==val도 아니라면 root.left와 root.right로 계속 호출해줘서 찾는 것이다. 

 

만약에, root.val==val 한 번이라도 된다면, self.searchBST(root, val)는 True가 되기 때문에 그 treenode가 반복되는 호출 속에서 나오게 된다. 

 

<총평>

오 내가 하나 풀다니

Happy coding!

Search in a Binary Search Tree - LeetCode