逐层排序二叉树所需的最少操作数目

标签: 树 广度优先搜索 二叉树

难度: Medium

给你一个 值互不相同 的二叉树的根节点 root 。

在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。

返回每一层按 严格递增顺序 排序所需的最少操作数目。

节点的 层数 是该节点和根节点之间的路径的边数。

示例 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, 105] 。
  • 1 <= Node.val <= 105
  • 树中的所有值 互不相同 。

Submission

运行时间: 279 ms

内存: 47.6 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        ans = 0
        q = [root]
        while q:
            a = []
            tmp = q
            q = []
            for node in tmp:
                a.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            n  = len(a)
            ans += n

            a = sorted(range(n), key = lambda i : a[i])

            vis = [False] * n
            for v in a:
                if vis[v]:
                    continue
                while not vis[v]:
                    vis[v] = True
                    v = a[v]
                ans -= 1
        return ans

Explain

题解的主要思路是使用宽度优先搜索（BFS）遍历二叉树的每一层，然后对每一层的节点值进行排序，并通过计算置换的最小循环次数来得到最小交换次数。对于每一层的节点值，我们首先记录它们的原始位置，然后对这些值进行排序。通过建立值和它们排序后位置的映射，我们可以确定每个节点值在排序后应该在的位置。然后，我们使用一个循环检测的方法来找出需要交换的最小循环数，从而得到将该层排序所需的最少操作数。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        ans = 0
        q = [root] # 使用队列实现BFS
        while q:
            a = [] # 存储当前层的节点值
            tmp = q
            q = []
            for node in tmp:
                a.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            
            n  = len(a)
            ans += n
            
            # 对当前层节点的索引按值进行排序
            a = sorted(range(n), key = lambda i : a[i])
            
            vis = [False] * n # 记录每个位置是否访问过
            for v in a:
                if vis[v]:
                    continue
                while not vis[v]:
                    vis[v] = True
                    v = a[v]
                ans -= 1 # 每完成一个循环，减少一次操作
        return ans

Explore

在解决问题时，我首先记录下每层节点值的原始位置，然后将这些值进行排序。通过排序，我们可以获得每个值应该位于的顺序位置。例如，如果一层的节点值为[3, 1, 2]，排序后变为[1, 2, 3]，则原始位置的值3应该位于排序后的最后一个位置。这样我们就可以通过排序后的位置索引来确定每个元素在排序后的正确位置。

在循环检测中，每完成一个循环意味着一组元素都被置于了正确的位置。考虑一个简单的例子，如果三个元素的最终位置是相互交换的（例如索引0的元素应该在索引1，索引1的元素应该在索引2，索引2的元素应该回到索引0），我们只需要两次交换操作就可以使所有元素各自到达正确位置。总的来说，一个循环中涉及n个元素，只需要n-1次交换，因此每完成一个循环，我们可以在总操作数中减少一次操作，以反映这种效率。

如果一个节点已经在正确的位置，这意味着在循环检测中该节点不需要进行任何交换。在算法实现中，这将被视作一个长度为1的循环，由于其已经处于正确位置，我们不需要对它执行任何操作。这种情况实际上可以提高算法的效率，因为它减少了必要的交换操作数量。对于这样的每个节点，我们不需要执行交换，只需标记为已访问即可，从而节省时间。

在宽度优先搜索（BFS）中，队列用于确保我们按照从上到下、从左到右的顺序访问节点。队列中的元素处理顺序不会影响最终解的正确性，因为每层的节点都会被完整地处理，并且它们的值被独立于其他层地排序和交换。然而，队列中的处理顺序可能会影响遍历的效率，特别是在队列操作（如入队和出队）的实现方式上。使用有效的队列操作可以优化BFS的时间复杂度，从而提高算法的总体效率。