按級別對二元樹進行排序的最少操作數

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

難度：中

主題：樹、廣度優先搜尋、二元樹

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

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

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

節點的等級是它與根節點之間的路徑上的邊數。

範例1：

• 輸入： root = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
• 輸出： 3
• 說明：
  • 交換 4 和 3。第 2 層變為 [3,4]。
  • 交換 7 和 5。第 3 級變為 [5,6,8,7]。
  • 交換 8 和 7。第 3 級變為 [5,6,7,8]。
  • 我們使用了 3 次操作，因此傳回 3。
  • 可以證明3是最少需要的運算次數。

範例2：

• 輸入： root = [1,3,2,7,6,5,4]
• 輸出： 3
• 說明：
  • 交換 3 和 2。第 2 層變為 [2,3]。
  • 交換 7 和 4。第 3 層變為 [4,6,5,7]。
  • 交換 6 和 5。第 3 層變為 [4,5,6,7]。
  • 我們使用了 3 次操作，因此傳回 3。
  • 可以證明3是最少需要的運算次數。

範例 3：

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

約束：

• 樹中的節點數量在 [1, 10⁵] 範圍內。
• 1 5
• 樹的所有值都是唯一。

提示：

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

解：

這個問題是關於以最少的運算元嚴格升序對二元樹的值進行逐級排序。在每次操作中，我們可以交換同一層級的兩個節點的值。目標是確定實現排序順序所需的此類操作的最少數量。

要點：

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

方法：

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

計劃：

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

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

<?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步：執行BFS以層級將節點分組:

   • 從根開始，逐層遍歷樹。
   • 對於每個節點，將其值附加到層級數組中的對應層級。

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

   • 對每個層級的值進行排序。
   • 使用基於循環的方法來計算將當前層級轉換為排序層級所需的最小交換。

3. 循環分解:

   • 對於每個未排序的元素，追蹤其循環（即它應該去的地方）並將元素標記為已存取。
   • 對於每個週期，所需的交換次數是週期長度減一。

4. 回傳交換總數:

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

演練範例：

範例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]

   • 已排序，無需交換。

總交換次數 = 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）。

總交換次數 = 1（1 級）2（2 級）= 3 次交換。

輸出：3

時間複雜度：

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

因此，總體時間複雜度為O(N log 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 次交換，如範例中詳述。

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

聯絡連結

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

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是按級別對二元樹進行排序的最少操作數的詳細內容。更多資訊請關注PHP中文網其他相關文章！