Leetcode 2471: Minimum Number of Operations to Sort a Binary Tree by Level
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 strictly increasing order.
Problem
Approach
Steps
Complexity
Input: You are given the root of a binary tree, represented as an array of unique integers, where each node's value is at its respective position in the level-order traversal of the tree.
Example: root = [1, 5, 4, 7, 6, 8, 9, null, null, null, null, 10]
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.
Output: Return the minimum number of swaps needed to make the tree's nodes at each level sorted in strictly increasing order.
Example: Output: 4
Constraints:
• The output should be an integer count.
Goal: The goal is to find the minimum number of swaps required to sort each level of the tree in strictly increasing order.
Steps:
• Perform a level-order traversal of the binary tree.
• For each level, find the minimum number of swaps required to sort the values at that level.
• Sum up the swaps for each level and return the total.
Goal: The tree is represented in level-order format, and each node has a unique value. The solution must handle a tree with up to 10^5 nodes efficiently.
Steps:
• 1 <= Node.val <= 10^5
• The number of nodes is between 1 and 10^5.
Assumptions:
• The input will always represent a valid binary tree with unique values.
• Input: Input: root = [1, 5, 4, 7, 6, 8, 9, null, null, null, null, 10]
• Explanation: At the second level, we need to swap the values 5 and 4 to make it [4, 5]. Similarly, at the third level, we need to swap 7 with 6, and then 8 with 7. This leads to a total of 4 swaps.
Approach: The solution involves traversing the tree level by level and sorting the node values at each level using the minimum number of swaps.
Observations:
• We need to track the node values at each level of the tree and count the swaps required to sort them.
• A level-order traversal will give us the node values at each level. Sorting these values with the minimum number of swaps is the main challenge.
Steps:
• Perform a level-order traversal of the tree using a queue.
• At each level, extract the node values and compute the minimum swaps needed to sort them.
• Accumulate the swaps required for each level and return the total.
Empty Inputs:
• The tree will not be empty, as per the problem's constraints.
Large Inputs:
• For large trees, ensure the solution handles up to 10^5 nodes efficiently.
Special Values:
• If the tree is already sorted at each level, no swaps will be needed.
Constraints:
• The number of nodes can be as large as 10^5, so the algorithm needs to be efficient enough to handle such large inputs.
int minimumOperations(TreeNode* root) {
int cnt = 0;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int sz = q.size();
vector<int> arr, idx(sz);
while(sz--) {
auto it = q.front();
q.pop();
arr.push_back(it->val);
if(it->left != NULL) q.push(it->left);
if(it->right!= NULL) q.push(it->right);
}
// cout << sz << " ";
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) { return arr[i] < arr[j]; });
for(int i = 0; i < idx.size(); i++)
for(; idx[i] != i; cnt++)
swap(idx[i], idx[idx[i]]);
}
return cnt;
}
1 : Function Declaration
int minimumOperations(TreeNode* root) {
This is the declaration of the function `minimumOperations`, which takes the root of a binary tree as input and returns the minimum number of operations needed to reorder the nodes.
2 : Variable Initialization
int cnt = 0;
The variable `cnt` is initialized to 0. It will count the number of operations (node swaps) required.
3 : Queue Initialization
queue<TreeNode*> q;
A queue `q` is created to help with level-order traversal (breadth-first search) of the binary tree.
4 : Push Root to Queue
q.push(root);
The root of the tree is added to the queue to start the level-order traversal.
5 : While Loop
while(!q.empty()) {
The loop continues as long as there are nodes in the queue. This represents level-order traversal.
6 : Size Calculation
int sz = q.size();
The variable `sz` stores the current size of the queue, which represents the number of nodes at the current level of the tree.
7 : Array Initialization
vector<int> arr, idx(sz);
Two vectors are initialized: `arr` to store the values of nodes at the current level, and `idx` to store their indices.
8 : Level Traversal
while(sz--) {
A loop that iterates over all nodes at the current level, decreasing `sz` until no more nodes are left.
9 : Queue Front Node
auto it = q.front();
The node at the front of the queue is accessed for processing.
10 : Pop Node from Queue
q.pop();
The node at the front of the queue is removed.
11 : Add Node Value to Array
arr.push_back(it->val);
The value of the current node is added to the `arr` vector.
12 : Left Child Check
if(it->left != NULL) q.push(it->left);
If the node has a left child, it is added to the queue for the next level of traversal.
13 : Right Child Check
if(it->right!= NULL) q.push(it->right);
If the node has a right child, it is added to the queue for the next level of traversal.
14 : Index Initialization
iota(idx.begin(), idx.end(), 0);
The `iota` function fills the `idx` vector with indices from 0 to `sz-1`, preparing it for sorting based on node values.
15 : Sorting Indices
sort(idx.begin(), idx.end(), [&](int i, int j) { return arr[i] < arr[j]; });
The `idx` vector is sorted in ascending order of the values in the `arr` vector, so we can track the correct positions of the nodes.
16 : Rearrangement Loop
for(int i = 0; i < idx.size(); i++)
A loop that iterates over all indices in the `idx` vector, which represents the sorted order of node values.
17 : Swap Nodes
for(; idx[i] != i; cnt++)
If the node is not in its correct position, we increment `cnt` and swap the node with the node at the correct index.
18 : Swap Elements in Array
swap(idx[i], idx[idx[i]]);
This line swaps the elements in the `idx` array to move the node to its correct position, counting each swap.
19 : Return Statement
return cnt;
The function returns the total number of swaps `cnt` required to sort the nodes.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The worst case occurs when sorting the values at each level takes O(log n) time for each level.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we need to store the values at each level of the tree.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus