Leetcode 2471. Minimum Number of Operations to Sort a Binary Tree by Level

문제

You are given the root of a binary tree with unique values.

In one operation, you can choose any two nodes at the same level and swap their values.

Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order.

The level of a node is the number of edges along the path between it and the root node.

• 동일한 레벨의 노드의 값을 서로 바꿀수 있다, 또한 모든 노드의 값은 유니크하다.
• 모든 레벨이 절대적으로 오름차순이 되게 하려면 최소 몇번을 바꿔야 하는가?

예시

• 4, 3 바꾸고
• 7, 5 바꾸고
• 8, 7 바꾼다.
• 총 3번 필요

제한

• 트리의 값은 $1 <= x <= 10^5$ 사이에 존재한다.
• 모든 트리의 값은 중복되지 않는다. ( unique )

풀이

• 이 문제는 트리처럼 보이지만 사실 정렬 문제에 가깝다.
• 주어진 배열을 최소 몇번 바꿔야 정렬이 되는지 구하는것이 중요하다.
• Cycle을 이용해 구할수 있다.

def swap(l: List[int]):
    s = list(sorted(enumerate(l), key=lambda k: k[1]))
    ans = 0
    check = [False] * len(l)

    for i in range(len(l)):
        cnt = 0
        while not check[i]:
            check[i] = True
            i = s[i][0]
            cnt += 1
        if cnt > 1:
            ans += (cnt - 1)
            
    return ans


class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        level = deque([root])
        values = deque([root.val])

        ans = 0

        while level:
            size = len(level)

            for _ in range(size):
                p = level.popleft()
                values.popleft()
                if p.left:
                    level.append(p.left)
                    values.append(p.left.val)
                if p.right:
                    level.append(p.right)
                    values.append(p.right.val)

            ans += swap(values)

        return ans