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

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

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: Tree、Breadth-First Search、Binary Tree
• \(\color{blue}\textsf{weekly Contest 319}\)

一、題目

You are given the root of a binary tree with unique values. In one operation, you can choose any two nodes at the same level and swap their values. Return the minimum number of operations needed to make the values at each level sorted in a strictly increasing order. The level of a node is the number of edges along the path between it and the root node.

Example 1:

• Input: root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• Output: 3
• Explanation:

• Swap 4 and 3. The 2nd level becomes [3,4].
• Swap 7 and 5. The 3rd level becomes [5,6,8,7].
• Swap 8 and 7. The 3rd level becomes [5,6,7,8].
  We used 3 operations so return 3.
  It can be proven that 3 is the minimum number of operations needed.

Example 2:

• Input: root = [1,3,2,7,6,5,4]
• Output: 3
• Explanation:

• Swap 3 and 2. The 2nd level becomes [2,3].
• Swap 7 and 4. The 3rd level becomes [4,6,5,7].
• Swap 6 and 5. The 3rd level becomes [4,5,6,7].
  We used 3 operations so return 3.
  It can be proven that 3 is the minimum number of operations needed.

Example 3:

• Input: root = [1,2,3,4,5,6]
• Output: 0
• Explanation: Each level is already sorted in increasing order so return 0.

Constraints:

• The number of nodes in the tree is in the range [1, 10^5].
• 1 <= Node.val <= 10^5
• All the values of the tree are unique.

二、分析

• 這一題最直觀的想法就是先將所有節點用 vector 記錄下來之後，分層去做 minSwaps。
• 注意到 minSwaps 的實現：想法是，n 個節點 swap 形成一個 cycle，代表進行了 n-1 次 swap，故我們可以觀察得：minSwaps 的次數會等於 n - cycles。

三、解題

1. DFS

• Time complexity: \(O(n\log n)\)
• Space complexity: \(O(n)\)

int minimumOperations(TreeNode* root) {
    vector<vector<int>> vec; 
    dfs(root, vec, 0);
    int res = 0;
    for (auto v : vec) {
        res += minSwaps(v);
    }
    return res;
}
void dfs(TreeNode* root, vector<vector<int>>& vec, int depth) {
    if (!root) return;
    if (depth == vec.size()) {
        vec.push_back({});
    }
    vec[depth].push_back(root->val);
    dfs(root->left, vec, depth+1);
    dfs(root->right, vec, depth+1);
}

int minSwaps(vector<int>& arr){
    int n = arr.size();
    map<int,int> map;
    for (int i = 0; i < n; i++) {
        map[arr[i]] = i;
    }
    vector<bool> vis(n, false);
    sort(arr.begin(), arr.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i] || map[arr[i]] == i) continue;
        int j = i, cycle = 0;
        while (!vis[j]) {
            vis[j] = true;
            j = map[arr[j]];
            cycle++;
        }
        if (cycle > 0) {
            ans += (cycle-1);
        }
    }
    return ans;
}

回目錄 Catalog