题目描述
思路解析动画文字版
记牢这一句:一层的最少交换次数,等于本层节点数减去环的个数。落到代码里就是把每层的值换算成名次,再用环排序数交换。下面从第 0 层开始,一层一层走。
总览 · 这棵树分三层：先把整棵树看清楚。层数是按到根走了几条边算的:根 45 在第 0 层;它的两个孩子 80、30 在第 1 层;最底下 50、70、20、90 在第 2 层。同一层内部才能互相交换,跨层不行。所以这题拆成三道互不相干的小题:每一层各自排好,把次数加起来。
第 0 层 · 读入本层的值：第 0 层紫色高亮,只有一个根节点 45。一个数不用比,天生就是升序,一次都不用换。它这层贡献 0。别小看这一步,它提醒我们:节点数是 1 的层永远 0 次。
第 0 层 · 单节点,0 次：这一层就一个 45,已经有序,变绿表示排好了,本层交换 0 次,累计答案还是 0。收工,进下一层。
第 1 层 · 读入本层的值：把第 1 层紫色高亮起来,从左到右是 80、30。目标是把它排成升序 30、80。同一层的值可以任意两两交换,现在的问题就变成:最少换几次能从当前顺序变成升序。
第 1 层 · 把值换算成名次：关键一步:把每个值换成它在升序里排第几,从 0 数起。80 是第 1 名,30 是第 0 名。于是这一层的位置序列就变成名次 1、0。排好序的样子,就是名次从左到右正好是 0、1,顺次排开。
第 1 层 · 盯住位置 0：轮到位置 0,紫色点亮它。它现在住着 80,这个值的名次是 1,不等于位置号 0,说明它坐错了地方。那就动手,把它送回名次 1 对应的位置去。
第 1 层 · 第 1 次交换：看位置 0,它现在住着 80,这个值的名次是 1,该去位置 1。那就直接把位置 0 和位置 1 的值对换,红色标出这两个正在交换的节点。换完位置 1 住进了 80,名次刚好是 1,它安家了。位置 0 又换来 30,还得继续看它归不归位。这一层已经换了 1 次,累计答案到 1。
第 1 层 · 位置 0 归位：换到现在,位置 0 住的值是 30,名次 0,终于等于位置号了,这一整条环理顺了。位置 0 变绿归位。这就是环排序的节奏:盯住一个位置,把不属于它的值一步步顶回各自的家,顺手也把沿途的位置都安顿好。
第 1 层 · 位置 1 已归位：轮到位置 1。它现在住的值是 80,名次是 1,正好等于位置号 1,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
第 1 层 · 结算,用了 1 次：第 1 层全部变绿,从左到右是 30、80,严格递增排好了。这一层一共换了 1 次。回头验证那条结论:本层 2 个节点,拆成了 1 个环,2 减 1 正好是 1,对得上。累计答案现在是 1。
第 2 层 · 读入本层的值：把第 2 层紫色高亮起来,从左到右是 50、70、20、90。目标是把它排成升序 20、50、70、90。同一层的值可以任意两两交换,现在的问题就变成:最少换几次能从当前顺序变成升序。
第 2 层 · 把值换算成名次：关键一步:把每个值换成它在升序里排第几,从 0 数起。50 是第 1 名,70 是第 2 名,20 是第 0 名,90 是第 3 名。于是这一层的位置序列就变成名次 1、2、0、3。排好序的样子,就是名次从左到右正好是 0、1、2、3,顺次排开。
第 2 层 · 盯住位置 0：轮到位置 0,紫色点亮它。它现在住着 50,这个值的名次是 1,不等于位置号 0,说明它坐错了地方。那就动手,把它送回名次 1 对应的位置去。
第 2 层 · 第 1 次交换：看位置 0,它现在住着 50,这个值的名次是 1,该去位置 1。那就直接把位置 0 和位置 1 的值对换,红色标出这两个正在交换的节点。换完位置 1 住进了 50,名次刚好是 1,它安家了。位置 0 又换来 70,还得继续看它归不归位。这一层已经换了 1 次,累计答案到 2。
第 2 层 · 第 2 次交换：看位置 0,它现在住着 70,这个值的名次是 2,该去位置 2。那就直接把位置 0 和位置 2 的值对换,红色标出这两个正在交换的节点。换完位置 2 住进了 70,名次刚好是 2,它安家了。位置 0 又换来 20,还得继续看它归不归位。这一层已经换了 2 次,累计答案到 3。
第 2 层 · 位置 0 归位：换到现在,位置 0 住的值是 20,名次 0,终于等于位置号了,这一整条环理顺了。位置 0 变绿归位。这就是环排序的节奏:盯住一个位置,把不属于它的值一步步顶回各自的家,顺手也把沿途的位置都安顿好。
第 2 层 · 位置 1 已归位：轮到位置 1。它现在住的值是 50,名次是 1,正好等于位置号 1,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
第 2 层 · 位置 2 已归位：轮到位置 2。它现在住的值是 70,名次是 2,正好等于位置号 2,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
第 2 层 · 位置 3 已归位：轮到位置 3。它现在住的值是 90,名次是 3,正好等于位置号 3,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
第 2 层 · 结算,用了 2 次：第 2 层全部变绿,从左到右是 20、50、70、90,严格递增排好了。这一层一共换了 2 次。回头验证那条结论:本层 4 个节点,拆成了 2 个环,4 减 2 正好是 2,对得上。累计答案现在是 3。
小结 · 为什么是节点数减环数：把第 2 层单独拎出来品一品。它的名次序列本来是 1、2、0、3。跟着箭头走:位置 0 想去 1,位置 1 想去 2,位置 2 又指回 0,这三个位置转成一个长度 3 的大环;位置 3 的名次就是 3,自己指自己,是个长度 1 的自环。一个长度 k 的环,理顺它要 k 减 1 次交换;所以 3 环花 2 次、自环花 0 次,合起来 2 次。节点数减环数,就是这么来的。
回放 · 三层加起来,答案 3：三层全部排好,回放一遍总账:第 0 层单节点 0 次,第 1 层 80 和 30 对换 1 次,第 2 层理顺那个 3 环用了 2 次。零加一加二,一共 3 次,跟开头说的 3 完全对上。整道题就是广度优先分层,每层名次映射再环排序,把各层次数加起来。
边界想清:单节点或本就升序都是 0 次;某层只有两个节点且逆序时,一次对换就够。
面试重点:分层加名次映射加环排序、最少交换等于节点数减环数、复杂度 O(n log n) 与 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass 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复杂度
- 时间：O(n log n)，n 是节点总数。每层大小为 k 时,排序取名次是 O(k log k),建映射 O(k),环排序每次交换至少归位一个值、整层是 O(k)。各层 k 相加等于 n,排序项相加不超过 O(n log n),是整体上界
- 空间：O(n)，按峰值算。队列在最宽那一层最多同时装下该层所有节点;每层还要一份值数组和名次映射。最坏一层宽到接近 n,所以峰值是 O(n),与节点总数同阶
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么最少交换等于节点数减环数?
追问时间和空间是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
到达首都的最少油耗
LeetCode 2477 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题