[BST*]99클럽 코테 스터디 13일차 TIL + 0783-search-in-a-binary-search-tree

783. Search in a Binary Search Tree

Easy

---

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

----

총 소요시간 : 1H 40M

<내코드>

# 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.right, val)
        else:
            return self.searchBST(root.left, val)
    # def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    #     data = root

    #     while root is not None:
    #         if data == val:
    #             return self.subTree(root)
    #         elif data < val: #찾으려는 값이 더 크면 오른쪽으로
    #             return self.searchBST(root.right, val)
    #         elif data > val:
    #             return self.searchBST(root.left, val)

    #     return None

    # def subTree(self, root : Optional[TreeNode]) -> Optional[TreeNode]:
    #     data = root.val
    #     subTree_list = TreeNode(data)

    #     if data is not None:
    #         subTree_list.left = TreeNode(root.left)
    #         subTree_list.right = TreeNode(root.right)

    #     return subTree_list

 

 

1. 헤맨부분

- 이진탐색트리에 대한 용도 (해시로도 충분히 탐색이 가능하지 않는가?)

=> BST가 O(h) [h == 높이] / 해시테이블이 O(1) 로서 해시테이블이 더 효율적이지만, 

순서를 정해주는 경우 BST가 더 용이하다.

 

정리하면 세트, 딕셔너리의 key가 정렬된 상태가 필요하다면 연산의 효율성이 다소 낮아짐에도 불구하고 BST가 필요하다.

 

- 반복문과 재귀를 이중으로 사용해버림

=> 

    # def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    #     data = root

    #     while root is not None:
    #         if data == val:
    #             return self.subTree(root)
    #         elif data < val: #찾으려는 값이 더 크면 오른쪽으로
    #             return self.searchBST(root.right, val)
    #         elif data > val:
    #             return self.searchBST(root.left, val)

    #     return None

while을 빼던가, 재귀를 빼던가 둘 중 하나를 했어야했음

특히 정답코드의 조건문 간에 모두가 return 이 있는 이유는 한쪽으로 조건이 갈라지면 더이상 그쪽으로 갈 일이 전혀 없고 점점 깊이를 더해가야하기 때문임

즉 순회가 아니라 탐색이기 때문임

 

- root 라는 인자 자체가 return 이 되어서 subtree가 될 수있는가?

=> root 자체가 재귀를 하면서 sub tree가 충분히 될 수 있음 

왜냐하면 처음부터 들어오는 인자타입이 그러하기 때문임

<모범사례>

from typing import Optional

# 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.right, val)
        else:
            return self.searchBST(root.left, val)

# Example usage
# Constructing the tree [4,2,7,1,3]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

solution = Solution()
result = solution.searchBST(root, 2)
# The result will be the subtree rooted at the node with value 2

<보충학습>

1. BST 학습

삽입 : 저장하기 위한 위치를 찾아가는 것 (기존 값과 비교하여 left, right 를 비교하면서 찾아감)

-> 이 경우 삽입되어야하는 위치에 값이 있는경우 그 값을 다른곳으로 이동시켜야함

 

탐색(검색) : 마찬가지로 비교하면서 찾아감

삭제 : leaf 인지 여부에 따라 달리 판단이됨 (추후 학습)