#2471
Minimum Number of Operations to Sort a Binary Tree by Level
pupil · 505 · lc medium +27 · verified · 74.2% accepted · 1,249 likes · top 85%
Description
Given the root of a binary tree with unique node values, each operation lets you pick any two nodes at the same level and swap their values. Return the minimum number of such operations required to make every level's values sorted in strictly increasing order.
A node's level is defined by the number of edges on the path from the root to that 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.
Code
1
2
3
4
5
6
7
8
9