✅ [Python] use cycle-sort to swap values, not nodes (explained)
\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.\n*\nThis solution employs a Breadth First Search tree level-by-level traversal with counting of permutations on
**\u2705 IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE.**\n****\nThis solution employs a Breadth First Search tree level-by-level traversal with counting of permutations on each level (using cycle-sort simulation). Time complexity is log-linear: **O(N\\*logN)**. Space complexity is linear: **O(N)**.\n\n**Comment.** The key observation here is that we are not asked to swap nodes, just sort their values on each level. Thus, the strategy to solve this problem is as follows:\n1. Do a level-by-level traversal using BFS and consider each layer of nodes independently.\n2. Extract values from each layer and count the number of permutations needed to sort them.\n\n**Python.**\n```\nclass Solution:\n    def minimumOperations(self, root: Optional[TreeNode]) -> int:\n        \n        nodes, count = deque([root]), 0\n        \n        def perm(arr):                                            # this function simulates cycle sort,\n            pos = {m:j for j,m in enumerate(sorted(arr))}         # namely, traverses every cycle in\n            vis, tot = [0] * len(arr), 0                          # the permutation of elements and \n            for i in range(len(arr)):                             # counts the number of swaps \n                cnt = 0\n                while not vis[i] and i != pos[arr[i]]:            # it is known that cycle sort is the\n                    vis[i], i = 1, pos[arr[i]]                    # sorting algorithm with the minmal\n                    cnt += 1                                      # number of memory operations (swaps)\n                tot += max(0, cnt-1)                              # needed to sort an array\n            return tot\n                    \n        while nodes:\n            vals = []\n            for _ in range(len(nodes)):                            # [1] this code performs a level-by-level\n                n = nodes.popleft()                                #     BFS scan of the tree and extracts\n                vals.append(n.val)                                 #     a list of values \'vals\' for each level\n                if n.left  : nodes.append(n.left)\n                if n.right : nodes.append(n.right)\n            count += perm(vals)                                    # [2] each level is sorted independently\n            \n        return count\n```
[]