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
- Levels are independent, so the answer is the sum of the minimum swaps for each level.
- For a level with values
v, the minimum swaps to sort it equalssum over cycles of (cycle length - 1)in the permutation that maps the current positions to the sorted positions. - Collect each level with BFS, compute its sorted target, then count cycle lengths.
- 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.
🧩 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