按级别对二叉树进行排序的最少操作数

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中文网其他相关文章！