2471。依等級對二元樹進行排序的最少操作數(shù)

難度：中

主題：樹、廣度優(yōu)先搜尋、二元樹

您將獲得一個二元樹的根，其中具有唯一值。

在一次操作中，您可以選擇任兩個同一層級的節(jié)點並交換它們的值。

傳回使每個等級的值依嚴格遞增順序排序所需的最少操作數(shù).

節(jié)點的等級是它與根節(jié)點之間的路徑上的邊數(shù)。

範(fàn)例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ù)。

範(fàn)例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ù)。

範(fàn)例 3：

• 輸入： root = [1,2,3,4,5,6]
• 輸出： 0
• 說明：每個等級都已按升序排序，因此傳回 0。

約束：

• 樹中的節(jié)點數(shù)量在 [1, 10⁵] 範(fàn)圍內(nèi)。
• 1 5
• 樹的所有值都是唯一。

提示：

1. 我們可以將值逐級分組並獨立求解每個組。
2. 進行 BFS 逐層將數(shù)值分組。
3. 找出對每個層級的陣列進行排序的最小交換次數(shù)。
4. 迭代數(shù)組時，檢查當(dāng)前元素，如果不在正確的索引中，則將該元素替換為應(yīng)該出現(xiàn)的元素的索引。

解：

這個問題是關(guān)於以最少的運算元嚴格升序?qū)Χ獦涞闹颠M行逐級排序。在每次操作中，我們可以交換同一層級的兩個節(jié)點的值。目標(biāo)是確定實現(xiàn)排序順序所需的此類操作的最少數(shù)量。

要點：

1. 二元樹等級：二元樹的每個等級都應(yīng)具有嚴格按升序排序的值。
2. 唯一值：所有節(jié)點都有唯一值，由於沒有重複項，因此排序更容易。
3. 用於層級分組的 BFS：使用廣度優(yōu)先搜尋 (BFS) 遍歷樹並按層級將節(jié)點分組。
4. 最小交換次數(shù)：對於每個級別，我們需要找到對該級別的節(jié)點值進行排序所需的最小交換次數(shù)。
5. 約束：樹最多可以有 10^5 個節(jié)點，因此解必須有效率。

方法：

1. BFS 遍歷：執(zhí)行 BFS 遍歷樹並收集每一層節(jié)點的值。
2. 對每個級別進行排序：對於每個級別，計算按嚴格升序?qū)χ颠M行排序的最小交換次數(shù)。
3. 循環(huán)分解：最小化交換的關(guān)鍵觀察是，對陣列進行排序可以看作是循環(huán)中交換元素。每個循環(huán)錯放元素的最小交換次數(shù)是循環(huán)長度減一。
4. 累積掉期：將每個等級的掉期相加，得到所需的掉期總數(shù)。

計劃：

1. BFS：使用 BFS 遍歷樹，收集每一層的節(jié)點。
2. 將每個等級排序：對每個等級的值進行排序並計算最小交換次數(shù)。
3. 計算交換：使用循環(huán)分解來找到對每個層級的節(jié)點進行排序所需的最小交換。

讓我們用 PHP 實作這個解：2471。依等級對二元樹進行排序的最少操作數(shù)

<?php
/**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

解釋：

1. 第1步：執(zhí)行BFS以層級將節(jié)點分組:

   • 從根開始，逐層遍歷樹。
   • 對於每個節(jié)點，將其值附加到層級數(shù)組中的對應(yīng)層級。

2. 第 2 步：對於每個級別，計算對值進行排序的最小交換:

   • 對每個層級的值進行排序。
   • 使用基於循環(huán)的方法來計算將當(dāng)前層級轉(zhuǎn)換為排序?qū)蛹壦璧淖钚〗粨Q。

3. 循環(huán)分解:

   • 對於每個未排序的元素，追蹤其循環(huán)（即它應(yīng)該去的地方）並將元素標(biāo)記為已存取。
   • 對於每個週期，所需的交換次數(shù)是週期長度減一。

4. 回傳交換總數(shù):

   • 對每個等級所需的交換量求和並回傳總數(shù)。

演練範(fàn)例：

範(fàn)例1：

輸入樹：

<?php
/**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

等級：

• 0級：[1]
• 1 級：[4, 3]
• 2 級：[7,6,8,5]
• 3 級：[9, 10]

1. 1 級: [4, 3]

   • 將其排序為 [3, 4]，並進行 1 次交換（交換 4 和 3）。

2. 2 級：[7,6,8,5]

   • 將其排序為 [5, 6, 7, 8]，並進行 2 次交換（交換 7 和 5，交換 8 和 7）。

3. 3 級: [9, 10]

   • 已排序，無需交換。

總交換次數(shù) = 1（1 級）2（2 級）= 3 次交換。

輸出：3

範(fàn)例2：

輸入樹：

        1
       / \
      4   3
     / \ / \
    7  6 8  5
             \
              9
               \
                10

等級：

• 0級：[1]
• 1 級：[3, 2]
• 2 級：[7,6,5,4]

1. 1 級: [3, 2]

   • 將其排序為 [2, 3]，並進行 1 次交換（交換 3 和 2）。

2. 2 級：[7,6,5,4]

   • 將其排序為 [4, 5, 6, 7]，並進行 2 次交換（交換 7 和 4，交換 6 和 5）。

總交換次數(shù) = 1（1 級）2（2 級）= 3 次交換。

輸出：3

時間複雜度：

1. BFS: O(N) 其中 N 是樹中的節(jié)點數(shù)。
2. 對每個等級進行排序：對每個等級的值進行排序需要O(L log L)，其中L 是目前層級的節(jié)點數(shù)。在最壞的情況下，總排序複雜度為 O(N log N).
3. 循環(huán)分解：每個等級O(L)。

因此，總體時間複雜度為O(N log N)，在給定約束的情況下，這已經(jīng)足夠高效了。

輸出範(fàn)例：

對於輸入樹：

<?php
/**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

輸出為 3 次交換，如範(fàn)例中詳述。

此解決方案透過使用 BFS 按層級對節(jié)點進行分組並循環(huán)分解來有效計算對二元樹的每個層級進行排序所需的最小交換次數(shù)，以最小化交換次數(shù)。 O(N log N) 的時間複雜度是處理最多具有 10^5 個節(jié)點的樹的最佳選擇。

聯(lián)絡(luò)連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是按級別對二元樹進行排序的最少操作數(shù)的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！