Problem Statement
Medium
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, 105].
1 <= Node.val <= 105- All the values of the tree are unique.
/**
* 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:
void swap(vector<int> &arr,int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int findMinSwaps(queue<TreeNode*>q){
vector<int> arr;
while(!q.empty()){
arr.push_back(q.front()->val);
q.pop();
}
int ans = 0, N=arr.size();
vector<int>temp = arr;
map <int, int> h;
sort(temp.begin(), temp.end());
for (int i = 0; i < N; i++)
h[arr[i]] = i;
for (int i = 0; i < N; i++){
if (arr[i] != temp[i]){
ans++;
int init = arr[i];
swap(arr, i, h[temp[i]]);
h[init] = h[temp[i]];
h[temp[i]] = i;
}
}
return ans;
}
int minimumOperations(TreeNode* root) {
int res=0;
queue<TreeNode*> q;
q.push(root);
int ct=1;
while (!q.empty()) {
TreeNode* node = q.front();
ct--, q.pop();
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
if(!ct)
ct=q.size(), res+=findMinSwaps(q);
}
return res;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minimumOperations(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
int nodesAtLevel = 1, currLevel = 0, res = 0;
q.offer(root);
List<Integer> nodesToSort = new ArrayList<>();
while (!q.isEmpty()) {
TreeNode top = q.poll();
if (top.left != null) {
q.offer(top.left);
nodesToSort.add(top.left.val);
}
if (top.right != null) {
q.offer(top.right);
nodesToSort.add(top.right.val);
}
if (--nodesAtLevel == 0) {
nodesAtLevel = q.size();
currLevel++;
res += calcSwapOperations(nodesToSort);
nodesToSort.clear();
}
}
return res;
}
private int calcSwapOperations(List<Integer> nodesToSort) {
List<Integer> target = new ArrayList<>(nodesToSort);
Collections.sort(target);
Map<Integer, Integer> ogMap = new HashMap<>();
for (int i = 0; i < nodesToSort.size(); i++)
ogMap.put(nodesToSort.get(i), i);
int numsSwap = 0;
for (int i = 0; i < target.size(); i++) {
int og = nodesToSort.get(i), tgt = target.get(i);
if (og != tgt) {
numsSwap++;
int swapIdx = ogMap.get(tgt);
nodesToSort.set(i, tgt);
nodesToSort.set(swapIdx, og);
ogMap.put(tgt, i);
ogMap.put(og, swapIdx);
}
}
// System.out.println(nodesToSort);
// System.out.println(numsSwap);
return numsSwap;
}
}