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:
[1, 105].1 <= Node.val <= 105This approach involves performing a breadth-first search (BFS) to traverse the tree level by level. For each level, extract the nodes and determine the minimum number of swaps required to sort the nodes in increasing order.
To determine the minimum number of swaps, consider each level as an array and apply a cycle detection method over it. The size of cycles can determine how many swaps are needed because each cycle in a permutation corresponds to a number of swaps to sort it.
The solution consists of two main parts:
1. Compute the levels using BFS.
2. For each level, compute the minimum number of swaps required to sort the nodes using a cycle detection method. The sum of these swaps for all levels is the final answer.
Java
Time Complexity: O(n log n), where n is the number of nodes, due to sorting operations per level.
Space Complexity: O(n) to store level arrays and indices.
In this approach, we still traverse the levels of the binary tree using DFS in addition to temporarily capturing the values at each level, then directly modifying the tree nodes to achieve the desired order.
It leverages an in-place sorting strategy to ensure minimal swaps are performed on elements by managing their positions directly at the tree level, albeit with a DFS traversal initially to fetch values.
The JavaScript solution uses DFS to traverse and collect nodes at each level, then determines the minimum swap count with an index mapping and cycle detection strategy. This helps retain the order directly by working with references to tree nodes.
C#
Time Complexity: O(n log n) due to in-level sorting operations.
Space Complexity: O(n) for capturing all nodes across the tree depths.
| Approach | Complexity |
|---|---|
| Approach with BFS and Cycles | Time Complexity: O(n log n), where n is the number of nodes, due to sorting operations per level. |
| DFS for Level Order with In-Place Reordering | Time Complexity: O(n log n) due to in-level sorting operations. |
Minimum Number of Operations to Sort a Binary Tree by Level - Leetcode 2471 - Python • NeetCodeIO • 7,322 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Sort a Binary Tree by Level with our built-in code editor and test cases.
Practice on FleetCode