Index Array
We do a level-order traverse using two queues.\n\nFor each level, we collect values. We use an index array (0...n - 1) to normalize those values.\n\nThen, we sw
We do a level-order traverse using two queues.\n\nFor each level, we collect values. We use an index array (`0...n - 1`) to normalize those values.\n\nThen, we swap indexes until all of them are in the correct position. \n\nThis takes O(n log n), instead of O(n ^ 2) if we search for the next smallest element.\n\n> Example: node values are `[7, 11, 3, 5, 2]`. \n> The index array, after sorting, will look like this: `[3, 4, 1, 2, 0]`.\n> We will do the following swaps:\n> `[3, 4, 1, 2, 0]`: initial state.\n> `[2, 4, 1, 3, 0]`: swap `3` and `2`, so `3` is in the right place (`i == ids[i]`).\n> `[1, 4, 2, 3, 0]`: swap `2` and `1`.\n> `[4, 1, 2, 3, 0]`: swap `1` and `4`.\n> `[0, 1, 2, 3, 4]`: swap `4` and `0`.\n> This approach needs up to O(n) swaps, and the overall complexity is O(sort).\n\n**C++**\n```cpp\nint minimumOperations(TreeNode* root) {\n    int res = 0;\n    vector<TreeNode*> q{root};\n    while(!q.empty()) {\n        vector<TreeNode*> q1;\n        vector<int> vals, ids(q.size());\n        for (auto n : q) {\n            vals.push_back(n->val);\n            if (n->left != nullptr)\n                q1.push_back(n->left);\n            if (n->right != nullptr)\n                q1.push_back(n->right);\n        }\n        iota(begin(ids), end(ids), 0);\n        sort(begin(ids), end(ids), [&](int i, int j){ return vals[i] < vals[j]; });\n        for (int i = 0; i < ids.size(); ++i)\n            for (; ids[i] != i; ++res)\n                swap(ids[i], ids[ids[i]]);\n        swap(q, q1);\n    }\n    return res;\n}\n```
['C']