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

题目地址：

https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/description/

给定一个值互不相等的二叉树，可以对每一行进行重排，重排的过程中每一步允许交换两个节点的值，问要将整棵树的每一行都变成严格单调增，至少需要多少步。

问题最后划归为，给定一个数字各不相同的数组$A$，允许交换两个数的位置，要将其升序排列至少需要多少步。这是个经典的数学问题。先将$A$进行保序离散化，最小值离散化为$0$（为$1$也可以，如果为$1$那就将离散化之后的数组视为$1\sim n$上的置换。为$0$则视为$0\sim n-1$上的置换），将$A$视为一个置换，如果其恰好是一个轮换，那么最少交换次数即为这个轮换的长度减$1$（即元素个数减$1$）证明可以参考https://blog.csdn.net/qq_46105170/article/details/119366423。如果$A$不是一个轮换而是多个轮换的乘积，则交换次数即为每个轮换的元素减$1$再求总和。代码如下：

class Solution {
 public:
  int minimumOperations(TreeNode* root) {
    if (!root) return 0;
    int res = 0;
    queue<TreeNode*> q;
    q.push(root);
    while (q.size()) {
      vector<int> v, ids;
      for (int i = q.size(); i--;) {
        auto t = q.front();
        q.pop();
        v.push_back(t->val);
        ids.push_back(ids.size());
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
      }

      sort(ids.begin(), ids.end(), [&](int i, int j) { return v[i] < v[j]; });
      for (int i = 0; i < ids.size(); i++) {
        if (ids[i] == -1) continue;
        int x = ids[i], len = 0;
        while (~ids[x]) {
          len++;
          int y = x;
          x = ids[y];
          ids[y] = -1;
        }

        res += len - 1;
      }
    }

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度$O({\sum }_i{n}_i\log n_i)$，$n_i$为二叉树每一行的节点个数，空间$O(n)$，$n$为节点总个数。