题目地址：

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

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

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

class Solution {public:int minimumOperations(TreeNode* root) {if (!root) return 0;int res = 0;queue q;q.push(root);while (q.size()) {vector 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;}
};

时间复杂度O(∑inilog⁡ni)O(\sum_i n_i\log n_i)O(∑i​ni​logni​)，nin_ini​为二叉树每一行的节点个数，空间O(n)O(n)O(n)，nnn为节点总个数。