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

發表於 | 分類於

problem

solution

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * 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:
    
int findMinSwap(vector<int> &arr, int n)
{
    // temporary vector to store values, along with its index in the original vector
    vector<pair<int, int>> temp(n);
    for (int i = 0; i < n; i++)
    {
        // values in the vector
        temp[i].first = arr[i];
        // index of the particular value.
        temp[i].second = i;
    }


    //sort the temp vector according to the values
    sort(temp.begin(), temp.end());
    // variable to store the answer
    int minimum_swaps = 0;
    int i = 0;
    while (i < n)
    {
        // If there is no need to swap then continue
        if (temp[i].second == i or temp[i].first == arr[i])
        {
            ++i;
            continue;
        }
        else
        {
            // swap the values accordingly
            swap(temp[i].first, temp[temp[i].second].first);
            // swap the indices also within the temp array also
            swap(temp[i].second, temp[temp[i].second].second);
            // stay on the same position until, we fulfill the criterion
            if (temp[i].second != i)
                i--;
        }
        //increment the answer
        minimum_swaps++;
        // move to the next index
        ++i;
    }
    return minimum_swaps;
}

    
     vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root)return ret;
        queue<TreeNode *>q({root});
        while(!q.empty()){
            int size = q.size();
            vector<int> level;
            for(int i=0;i<size;++i){
                
                TreeNode *p =  q.front();
                q.pop();
                level.push_back(p->val);
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
            ret.push_back(level);
            
        }
        return ret;
    }
    
    int minimumOperations(TreeNode* root) {
        
        vector<vector<int>> level = levelOrder(root);
        int ret = 0;
        for(vector arr:level)
        {
            ret+=findMinSwap(arr, arr.size());
            
        }
        return ret;
        
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(n)