⚡Flashcard Drill➔
NeetCode #427LC-2471MediumTrees
← Back to All Problems

#427 · #2471 · Minimum Number of Operations to Sort a Binary Tree by Level(逐层排序二叉树所需的最少操作数目)

📌 Problem Statement & Constraints

You are given the root of a binary tree. In one operation you may swap the values of two nodes on the same level. Return the minimum number of operations to make the values sorted in non-decreasing order at every level. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 10^5.

💡 Core Algorithmic Approaches

  1. Levels are independent, so the answer is the sum of the minimum swaps for each level.
  2. For a level with values v, the minimum swaps to sort it equals sum over cycles of (cycle length - 1) in the permutation that maps the current positions to the sorted positions.
  3. Collect each level with BFS, compute its sorted target, then count cycle lengths.
  4. The cycle decomposition is the standard result for "minimum swaps to sort a permutation".

💻 Benchmark Python3 Implementation

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        from collections import deque
        res = 0
        q = deque([root])
        while q:
            n = len(q)
            vals = []
            for _ in range(n):
                node = q.popleft()
                vals.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            # minimum swaps to sort this level = sum(cycle length - 1)
            pos = {v: i for i, v in enumerate(sorted(vals))}
            visited = [False] * n
            for i in range(n):
                if visited[i] or pos[vals[i]] == i:
                    visited[i] = True
                    continue
                cycle = 0
                j = i
                while not visited[j]:
                    visited[j] = True
                    j = pos[vals[j]]
                    cycle += 1
                res += cycle - 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): each level is sorted, and the total size across levels is n.
💾 Space Complexity
O(w) for the widest level.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the minimum swaps equals the number of misplaced elements: it is the cycle-based count, which can be much smaller.
  • Sorting the whole tree at once: swaps are only allowed within a level.
  • Using a nested-loop swap simulation: O(k^2) per level instead of O(k).
  • Forgetting the fixed points: an element already in place forms a cycle of length 1 and contributes 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems

中文速览与面试要点

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

给你一个 值互不相同 的二叉树的根节点 root。在一步操作中,你可以选择 同一层 中的任意两个节点,交换它们的值。返回使每一层都 按升序 排列所需的最少操作数。约束:树中的节点数在范围 [1, 10^5] 内;0 ≤ Node.val ≤ 10^5;所有 Node.val 互不相同。

核心要点

  • BFS 逐层 + 置换环计数(标准解) :对每一层,把该层的值序列与其升序序列比较,求「最少交换次数」。
  • 最少交换次数的公式 :把当前序列视为一个置换,找出所有 环 ,答案 = Σ(环长 − 1) 。
  • 为什么是 环长 − 1 :一个长度为 L 的环最少需要 L−1 次交换才能还原(每次交换最多修复一个位置)。
  • 实现 :建 值 → 目标位置 映射,用 visited 数组遍历每个环。

常见陷阱

  • 把最少交换次数算成「错位数 / 2」 :那只对「两两交换」的简单情形成立,置换环才是通用公式。
  • 忘记 visited[i] = True 的初始标记 : vals[i] == target[i] 的位置本身就「已就位」,必须标记为已访问,否则可能被误计入环。
  • 环长统计错误 :从 i 出发沿 pos[vals[j]] 走,直到回到已访问节点。
  • 用 BFS 时忘记把子节点入队 :会导致只处理根节点一层。

参考实现

from collections import deque

class Solution:
    def minimumOperations(self, root: 'TreeNode') -> int:
        res = 0
        q = deque([root])
        while q:
            level = [q.popleft() for _ in range(len(q))]
            vals = [n.val for n in level]
            target = sorted(vals)
            pos = {v: i for i, v in enumerate(target)}   # 值 -> 目标位置
            visited = [False] * len(vals)

            for i in range(len(vals)):
                if visited[i] or vals[i] == target[i]:
                    visited[i] = True
                    continue
                # 遍历置换环
                j = i
                clen = 0
                while not visited[j]:
                    visited[j] = True
                    j = pos[vals[j]]
                    clen += 1
                res += clen - 1                          # 环长 - 1

            for n in level:
                if n.left:
                    q.append(n.left)
                if n.right:
                    q.append(n.right)
        return res