LeetCode 题解工作台
逐层排序二叉树所需的最少操作数目
给你一个 值互不相同 的二叉树的根节点 root 。 在一步操作中，你可以选择 同一层 上任意两个节点，交换这两个节点的值。 返回每一层按 严格递增顺序 排序所需的最少操作数目。 节点的 层数 是该节点和根节点之间的路径的边数。 示例 1 ： 输入： root = [1,4,3,7,6,8,5,nu…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们先通过 `BFS` 遍历二叉树，找到每一层的节点值，然后对每一层的节点值进行排序，如果排序后的节点值与原节点值不同，则说明需要交换元素，交换元素的次数即为该层需要的操作数。 时间复杂度 $O(n \times \log n)$。其中 为二叉树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个 值互不相同 的二叉树的根节点 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- 树中的所有值 互不相同 。
解题思路
方法一：BFS + 离散化 + 元素交换
我们先通过 BFS 遍历二叉树，找到每一层的节点值，然后对每一层的节点值进行排序，如果排序后的节点值与原节点值不同，则说明需要交换元素，交换元素的次数即为该层需要的操作数。
时间复杂度 。其中 为二叉树的节点数。
# 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:
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def f(t):
n = len(t)
m = {v: i for i, v in enumerate(sorted(t))}
for i in range(n):
t[i] = m[t[i]]
ans = 0
for i in range(n):
while t[i] != i:
swap(t, i, t[i])
ans += 1
return ans
q = deque([root])
ans = 0
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans += f(t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting each level during minimum swap computation, and space complexity is O(n) for storing values of all levels during BFS traversal. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Does your solution correctly handle large binary trees with up to 105 nodes?
- question_mark
Can you explain how you calculate minimum swaps for a single level efficiently?
- question_mark
Have you considered that swaps are only allowed between nodes on the same level?
常见陷阱
外企场景- error
Trying to swap nodes across different levels instead of handling levels independently.
- error
Forgetting that node values are unique, which affects the cycle counting in minimum swap computation.
- error
Not using BFS and incorrectly mixing depth-first approaches that complicate level tracking.
进阶变体
外企场景- arrow_right_alt
Compute minimum operations when duplicate values are allowed, requiring value frequency tracking.
- arrow_right_alt
Determine minimum swaps to sort levels in non-strictly increasing order, modifying the target sequence criteria.
- arrow_right_alt
Optimize for very wide binary trees where storing entire levels might need streaming or partial storage.