99클럽 코테 스터디 13일차 TIL (Search in a Binary Search Tree) - LeetCode

1. 오늘의 학습 키워드

• 이진 트리
• 이진 탐색 트리
• 트리
• 트리 탐색

---

2. 문제: 700. Search in a Binary Search Tree

• 단계: Easy
• 주제: Tree, Binary Search Tree, Binary Tree

문제 설명

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2:

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints:

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= 107
• root is a binary search tree.
• 1 <= val <= 107

---

3. 나의 풀이

접근 방법

이 문제는 이진 탐색 트리 문제로 주어진 BST에서 val 을 루트로 하는 서브트리를 리턴하는 문제이다.

그럼 이진 탐색 트리가 뭔지를 알아야 한다.

---

이진 탐색 트리란?

정의:

1. 노드의 왼쪽 하위 트리에는 노드의 키(값)보다 작은 키가 있는 노드만 포함된다.
2. 노드의 오른쪽 하위 트리에는 노드의 키(값)보다 큰 키가 있는 노드만 포함된다.
3. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다.
4. 중복된 키(값)를 허용하지 않는다.

---

즉, 주어진 val 이 root값보다 작으면 왼쪽 서브트리로 향하고, 크면 오른쪽 서브트리로 향하도록 하고, root를 기존 root노드의 왼/오 서브트리의 root 노드로 변경하면 된다.

코드는 아래와 같다:

# 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
        """
        while root:
            if root.val < val:
                if root.right:
                    root = root.right
                else:
                    return
            elif root.val > val:
                if root.left:
                    root = root.left
                else:
                    return
            else:
                return root

---

4. 결론

이번 문제는 BST에서 탐색을 구현하는 기본적인 문제였다. 이진 탐색 트리를 한 번 정리 할 수 있는 좋은 기회였던것 같다.

읽어주셔서 감사합니다.