[파이썬/Python] Leet Code 700(Easy): Search in a Binary Search Tree

숨·2025년 9월 6일

코테

알고리즘 문제 풀이

목록 보기

127/128

📌 문제 : Leet Code 700

📌 문제 탐색하기

Node.val : 노드의 값 ( $1 ≤ Node.val ≤ 10^7$ )
val : 찾고자 하는 노드의 값 ( $1 ≤ val ≤ 10^7$ )

문제 풀이

이진 트리의 root값과 정수 val이 입력되었을 때 이진 트리에 있는 val가 같은 노드를 찾아 해당 노드가 루트인 서브 트리를 반환하는 문제이다.

이진 트리 연결 정보를 의미하는 root는 이미 이진 트리 방식으로 구성되어 있다.
하나씩 접근해 동일한 값을 찾고 그 노드의 left, right 값을 함께 반환하면 된다.
만약 없다면 None을 반환한다.

가능한 시간복잡도

트리 높이에 따라 결정 → 균형: $O(logn)$ , 편향: $O(n)$

최종 시간복잡도
최악의 경우에도 $O(n)=O(5000)$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

값에 따라 이진 트리 접근

📌 코드 설계하기

원하는 값이 없으면 빈 값 반환
노드 값이 원하는 값과 같으면 반환
노드 값이 원하는 값보다 크면 왼쪽 이동
노드 값이 원하는 값보다 작으면 오른쪽 이동

📌 시도 회차 수정 사항

트리 구조를 정의한 클래스를 보고, 입력된 root 리스트에 하나씩 접근해서 연결된 트리로 만들어줘야 한다고 생각했다.
함수에서 def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:라고 되어 있다.
- 이는 이미 root 자체가 이진 트리로 정의되어 있음을 확인할 수 있다 → 연결된 트리로 만들 필요 없이 바로 이용하는 식으로 구현했다.

📌 정답 코드

 # 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 not root:
            return None
        
        # 노드 값이 원하는 값과 같으면 반환
        if root.val == val:
            return root
        
        # 노드 값이 원하는 값보다 크면 왼쪽 이동
        elif root.val > val:
            return self.searchBST(root.left, val)
        # 노드 값이 원하는 값보다 작으면 오른쪽 이동
        elif root.val < val:
            return self.searchBST(root.right, val)