class Solution:

    def minimumOperations(self, root: Optional[TreeNode]) -> int:

        visit = [0 for _ in range(100001)]

        ans = 0

        def cycle_shape(h, v):

            identity = sorted(h)

            permutation = {}

            ret = 0

            for x, fx in zip(identity, h):

                permutation[x] = fx

            for node in h:

                if v[node] == 1:

                    continue

                count = 0

                while v[node] == 0:

                    v[node] = 1

                    node = permutation[node]

                    count += 1

                ret += count - 1

            return ret

        ch, height = 0, []

        queue = deque([(root, 0)])

        while queue:

            cur, depth = queue.popleft()

            if depth > ch:

                ans += cycle_shape(height, visit)

                ch += 1

                height = []

            if cur.left:

                height.append(cur.left.val)

                queue.append((cur.left, depth + 1))

            if cur.right:

                height.append(cur.right.val)

                queue.append((cur.right, depth + 1))

        return ans + cycle_shape(height, visit)

하필 이브에 나온 문제는 구현이 귀찮아서 버려둠.. 답은 알겠다만..

n-cycle은 n-1번 swap하면 identity map이 되고 이게 최소 횟수입니다