이진 트리의 두 번째 최소 노드

음수가 아닌 값을 가진 노드로 구성된 비어 있지 않은 특수 이진 트리가 주어지면 이 트리의 각 노드는 정확히 two 또는 zero 하위 노드를 가집니다. 노드에 두 개의 하위 노드가 있는 경우 이 노드의 값은 두 개의 하위 노드 중에서 더 작은 값입니다. 더 공식적으로는 속성root.val = min(root.left.val, root.right.val)이 항상 유지됩니다.

이러한 이진 트리가 주어지면 전체 트리의 모든 노드 값으로 구성된 집합에서 두 번째 최소값을 출력해야 합니다.

그러한 두 번째 최소값이 존재하지 않으면 대신 -1을 출력합니다.

예 1:



입력: 루트 = [2,2,5,null,null,5,7]
출력: 5
설명: 가장 작은 값은 2이고 두 번째로 작은 값은 5입니다.

예 2:



입력: 루트 = [2,2,2]
출력: -1
설명: 가장 작은 값은 2인데 두 번째로 작은 값이 없습니다.

제약:

트리의 노드 수가 [1, 25] 범위에 있습니다.

1 <= Node.val <= 231 - 1

root.val == min(root.left.val, root.right.val) 트리의 각 내부 노드에 대해.

해결책:

import heapq

# 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 inorder(self, root):
        if root:
            self.inorder(root.left)
            if root.val not in self.dup:
                heapq.heappush(self.heap, root.val)
                self.dup.add(root.val)
            self.inorder(root.right)

    def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
        self.heap = []
        self.dup = set()
        self.inorder(root)
        first = heapq.heappop(self.heap)
        if len(self.heap) > 0:
            second = heapq.heappop(self.heap)
            return second
        return -1