Second Minimum Node In a Binary Tree

•

문제 링크 : LeetCodeSecond Minimum Node In a Binary Tree - LeetCode

•

문제 설명 : 제공된 이진트리에서 두번째로 작은 숫자를 찾는다.

•

풀이 방법

◦

root.val = min(root.left.val, root.right.val) 라는 조건이 존재한다.

▪

이는 자식 노드가 절대 부모 노드보다 작아질 수 없는 구조이다.

▪

즉, 최소힙과 비슷한 구조이다.

◦

가장 작은 값은 Root임을 알 수 있으며, 자연스럽게 두 번째로 작은 값은 Root을 제외한 나머지 노드 중 가장 작은 값을 말하는 것이다.

•

시간복잡도 : O(N)O(N)O(N)

•

성공 코드

# 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 findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        
        # 가장 작은 값은 무조건 root이기 때문에, root보다 큰 값중 가장 작은 값 확인
        self.keys = set()

        def search_tree(node):
            self.keys.add(node.val)
            
            if not node.left and not node.right:
                return

            search_tree(node.left)
            search_tree(node.right)

        if root:
            self.keys.add(root.val)
            search_tree(root)
            self.keys.remove(root.val)

        return min(self.keys) if self.keys else -1
Python
복사