The binary tree has a different value at every node. In one operation, choose any two nodes at the same depth and exchange their values. Return the minimum number of operations needed so that, at every depth, the values read from left to right are strictly increasing.
The nodes you swap do not have to be adjacent. Only their values change; the tree structure stays the same. The root has depth 0, and each child is one level deeper than its parent.
Examples use level-order arrays. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.
Example 1:
Input: root = [8,6,2,9,3,7,1]
Output: 2Explanation: Swap 6 and 2 on the second level. On the third level, swap 9 and 1 to get [1,3,7,9]. Both levels are then sorted, using two operations in total.
Example 2:
Input: root = [5,2,8,1,4,6,9]
Output: 0Explanation: Every level already reads in strictly increasing order: [5], [2,8], and [1,4,6,9]. No swaps are needed.
Example 3:
Input: root = [10,4,7,8,null,2]
Output: 1Explanation: The deepest level reads [8,2], even though these nodes have different parents. Swapping their values makes that level [2,8]. The other levels are already sorted, so one operation suffices.
Constraints:
- The tree contains between 1 and 100000 nodes.
1 <= Node.val <= 100000- All node values are distinct.