給你一個值互不相同的二叉樹的根節(jié)點?root，在一步操作中，你可以選擇同一層上任意兩個節(jié)點，交換這兩個節(jié)點的值。返回每一層按嚴(yán)格遞增順序排序所需的最少操作數(shù)目。節(jié)點的層數(shù)是該節(jié)點和根節(jié)點之間的路徑的邊數(shù)。

示例?1 ：

輸入：

root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]

輸出：3

解釋：
- 交換 4 和 3 。第 2 層變?yōu)?[3,4] 。
- 交換 7 和 5 。第 3 層變?yōu)?[5,6,8,7] 。
- 交換 8 和 7 。第 3 層變?yōu)?[5,6,7,8] 。
共計用了?3 步操作，所以返回 3 。
可以證明?3 是需要的最少操作數(shù)目。
示例?2 ：

輸入：root = [1,3,2,7,6,5,4]??輸出：3

解釋：

- 交換 3 和 2 。第 2 層變?yōu)?[2,3] 。
- 交換 7 和 4 。第 3 層變?yōu)?[4,6,5,7] 。
- 交換 6 和 5 。第 3 層變?yōu)?[4,5,6,7] 。
共計用了?3 步操作，所以返回 3 。
可以證明?3 是需要的最少操作數(shù)目。
示例?3 ：

輸入：root = [1,2,3,4,5,6]? ?輸出：0

解釋：每一層已經(jīng)按遞增順序排序，所以返回?0 。

提示：

·樹中節(jié)點的數(shù)目在范圍?[1, 105]?。

·1 <= Node.val <= 105

·樹中的所有值互不相同。

分析:

先用bfs層序遍歷存下每一層的所有節(jié)點的值,然后對每一層的最小交換次數(shù)求和,對于一個待排序數(shù)組來說求最小交換次數(shù)使得它有序,可以利用求交換環(huán)獲得。首先利用一個數(shù)組把序列里面的數(shù)的原來位置利用一個數(shù)組來記錄一下，然后給原序列按照升序排序，我們知道了最終的結(jié)果，現(xiàn)在就是要如何從原來的位置，到達(dá)最終的位置的問題。

以樣例來說明:

下標(biāo)?1 2 3 4
排序前?7 6 8 5
排序后?5 6 7 8
觀察得7不在正確的位置上,所以與8交換,序列變?yōu)? 6 7 5,繼續(xù)看8也不在正確的位置上,與5交換得5 6 7 8,至此7,5,8全部訪問過,且三個元素構(gòu)成一個交換環(huán),6作為單點默認(rèn)成環(huán),所以一共兩個交換環(huán),要一個交換環(huán)內(nèi)所有的元素有序只需要交換該環(huán).size()-1次,即所有環(huán)得交換次數(shù)和為數(shù)組的大小-交換環(huán)的個數(shù)次。