BFS levelwise transversal+compare with sorted or dfs cycle lengths||29 ms Beats 97.95%
IntuitionUse BFS to perform levelwise transversal.
To count how many swaps by using comparing with sorted array.2nd approach computes the number of swaps using
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Use BFS to perform levelwise transversal.
To count how many swaps by using comparing with sorted array.

2nd approach computes the number of swaps using the following formula
$$
swaps=\sum_{cycle\ in\ G} |cycle|-1
$$
where `|cycle|` is the length for cycle & $G$ is the graph built by edges `(x, idx[x])` given by `id=[0,1,..qz-1]->[idx[x] for x in id ]`
A Math explanation is given. C++ & Python codes are made for the 2nd approach.
# Approach
<!-- Describe your approach to solving the problem. -->
[Please turn English subtiles if necessary]
[https://youtu.be/AMJMwSVl-fw?si=ETRVn__ujR83EUTo](https://youtu.be/AMJMwSVl-fw?si=ETRVn__ujR83EUTo)
1. construct a queue `q` holding `TreeNode*` for BFS
2. push `root` to `q`
3. Initialize `swaps=0`
4. BFS performs while `q` is not empty:
    * let `qz=|q|`
    * let `idx=[0, 1,...,qz-1]`
    * let `arr` contain the values for the nodes on this level
    * Perform the loop:
```
            for(int i=0; i<qz; i++){// BFS for this level
                auto node=q.front();
                q.pop();
                arr[i]=node->val;// store value in arr
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
```
5.  While performing the level transversal, there are 2 other things to do:
```
// each value is unique, no need for stable_sort
            sort(idx.begin(), idx.end(), [&](int i, int j){
                return arr[i]<arr[j];
            });
```
6. For coounting the swaps, it needs
```
for(int i=0; i<qz; ){
    int j=idx[i];
    if (j!=i){// recheck
        swaps++;
        swap(idx[i], idx[j]);
    }
    else i++; // next iteration
}
```
7. return `swaps`
8. A slight version is C-style version instead of queue & vector, C-array is used which is faster.
9. 2nd approach using DFS cycle lengths' formula is also done.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O(n\log n)$$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(n)$$
# Code BFS+ compare with sorted||C++ 43 ms Beats 95.31%|| 2nd C style version 29ms Beats 97.95%
```cpp []
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    static int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int swaps=0;
        while(!q.empty()){
            int qz=q.size();
            vector<int> idx(qz, 0);
            iota(idx.begin(), idx.end(), 0);
            vector<int> arr(qz, 0);
            for(int i=0; i<qz; i++){
                auto node=q.front();
                q.pop();
                arr[i]=node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            // each value is unique, no need for stable_sort
            sort(idx.begin(), idx.end(), [&](int i, int j){
                return arr[i]<arr[j];
            });
            for(int i=0; i<qz; ){
                int j=idx[i];
                if (j!=i){// recheck
                    swaps++;
                    swap(idx[i], idx[j]);
                }
                else i++; // next iteration
            }
        }
        return swaps;
    }
};


auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();

```
```cpp [C++ 2nd version]
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    static int minimumOperations(TreeNode* root) {
        TreeNode* q[100000];
        int front=0, back=0;
        q[back++]=root;
        int swaps=0;
        while(back-front>0){
            const int qz=back-front;
            int* idx=(int*)alloca(qz*sizeof(int));
            iota(idx, idx+qz, 0);
            int* arr=(int*)alloca(qz*sizeof(int));
            for(int i=0; i<qz; i++){
                auto node=q[front++];
                arr[i]=node->val;
                if(node->left) q[back++]=node->left;
                if(node->right) q[back++]=node->right;
            }
            // each value is unique, no need for stable_sort
            sort(idx, idx+qz, [&](int i, int j){
                return arr[i]<arr[j];
            });
            for(int i=0; i<qz; ){
                int j=idx[i];
                if (j!=i){// check twice
                    swaps++;
                    swap(idx[i], idx[j]);
                }
                else i++; // next iteration
            }
        }
        return swaps;
    }
};


auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
```
# 2nd approach swaps computing using DFS cycle lengths' formula||34ms

2nd approach deals with with cycle lengths. This approach is more Math. That one is related to the permutation group on `[0,1,..qz-1]`. That one is based on the fact that each permutation is a series of cyclic transformations.

A cyclic transformation can be denoted by $(i_0, i_1,..., i_k)$ which is fn fact $i_0 \to i_1, i_1 \to i_2,\cdots, i_{k-1} \to i_k, i_k\to i_0$. A cyclic transformation  of length k+1 can be performed by k  2-cycles(i.e. swaps).

The length's counting is using DFS.
![2471.png](https://assets.leetcode.com/users/images/26cf8804-07af-46e6-8bb0-ac78b56ec6ff_1734928536.6666222.png)
For better understanding the permuation, let's consider the nodes on 2th level. `arr=[7,6,8,5]`=> `idx=[2,1,3,0]` The permutations are listed by the following
```
0 1 2 3 <- identity
2 1 3 0 <- idx[x]
```
They can be represented by a cyclic transform `(0,2,3)` which has length 3. This cyclic transform of length 3 can be proceeded by 2 swaps `(2,3)` then `(0, 2)` (order cannot be reversed, `2=|cycle|-1=3-1`)
# C++ & Python codes for 2nd approach
```C++ []
const int N=50001;
class Solution {
public:
    inline static int dfs(int i, int* idx, bitset<N>& viz){
    //    cout<<i<<"->";
        if (viz[i]) return 0;
        viz[i]=1;
        int j=idx[i];
        return 1+dfs(j, idx, viz);
    }
    static int minimumOperations(TreeNode* root) {
        TreeNode* q[N];
        int front=0, back=0;
        q[back++]=root;
        int swaps=0;
        while(back-front!=0){
            int qz=back-front; 
            qz=(qz>0)?qz: qz+N;
            int* idx=(int*)alloca(qz*sizeof(int));
            iota(idx, idx+qz, 0);
            int* arr=(int*)alloca(qz*sizeof(int));
            for(int i=0; i<qz; i++){
                auto node=q[front];
                if (++front==N)  front=0;
                arr[i]=node->val;
                if(node->left) {
                    q[back]=node->left;
                    if (++back==N)  back=0;
                }
                if(node->right) {
                    q[back]=node->right;
                    if (++back==N)  back=0;
                }
            }
            // each value is unique, no need for stable_sort
            sort(idx, idx+qz, [&](int i, int j){
                return arr[i]<arr[j];
            });
            // cycle length count
            bitset<N> viz=0;
        //    cout<<"\n----\n";
            for(int i=0; i<qz; i++){
                if (!viz[i]) swaps+=dfs(i, idx, viz)-1;
            }
        }
        return swaps;
    }
};



auto init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 'c';
}();
```
```Python []
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        def dfs(i, idx, viz):
            if viz[i]: return 0
            viz[i]=True
            j=idx[i]
            return 1+dfs(j, idx, viz)

        q=deque()
        q.append(root)
        swaps=0
        while q:
            qz=len(q)
            arr=[0]*qz
            for i in range(qz):
                node=q.popleft()
                arr[i]=node.val
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            idx=sorted(range(qz), key = lambda k : arr[k])

            viz=[False]*qz
            for i in range(qz):
                if not viz[i]:
                    swaps+=dfs(i, idx, viz)-1
        return swaps
        
```
['Math', 'Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++', 'Python3']