2471。按級別對二叉樹進行排序的最少操作數(shù)

難度：中等

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

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

在一次操作中，您可以選擇任意兩個同一級別的節(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
• 說明：每個級別都已按升序排序，因此返回 0。

約束：

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

提示：

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

解決方案：

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

要點：

1. 二叉樹級別：二叉樹的每個級別都應(yīng)具有嚴格按升序排序的值。
2. 唯一值：所有節(jié)點都有唯一值，由于沒有重復(fù)項，因此排序更容易。
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)鍵觀察是，對數(shù)組進行排序可以看作是循環(huán)中交換元素。每個循環(huán)錯放元素的最小交換次數(shù)是循環(huán)長度減一。
4. 累積掉期：將每個級別的掉期相加，得到所需的掉期總數(shù)。

計劃：

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

讓我們用 PHP 實現(xiàn)這個解決方案：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)的方法來計算將當前級別轉(zhuǎn)換為排序級別所需的最小交換。

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

   • 對于每個未排序的元素，跟蹤其循環(huán)（即它應(yīng)該去的地方）并將元素標記為已訪問。
   • 對于每個周期，所需的交換次數(shù)是周期長度減一。

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

   • 對每個級別所需的交換量求和并返回總數(shù)。

演練示例：

示例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

示例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

時間復(fù)雜度：

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

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

輸出示例：

對于輸入樹：

<?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 次交換，如示例中詳述。

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

聯(lián)系鏈接

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

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

• 領(lǐng)英
• GitHub

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