题目描述
思路解析
一句话答案：LeetCode 2471 逐层排序二叉树的最少操作：按层广度优先取出每层的值，把值换成升序名次后用环排序，一层的最少交换等于节点数减环数，各层加总，时间 O(n log n)。
每层各自排成严格递增，最少换几次
给你一棵二叉树，值互不相同。一次操作能挑同一层里的任意两个节点对调它们的值；层数按到根走过的边数算。目标是让每层从左到右严格递增，问最少几次。以题面的 root=[45,80,30,50,70,20,90] 为例：根 45 在第 0 层，80、30 在第 1 层，50、70、20、90 在第 2 层，答案是 3。跨层不能换，这一条决定了整道题的拆法。
为什么不能把全树的值一起排
题目只准交换同一层的两个节点，跨层挪不动。把七个值当一整串去数交换，会算出把 20 搬去别层这种非法步骤，得数偏小。还有个易混点：最少交换不是逆序对，逆序对数的是相邻两两交换，而这里任意两个位置都能直接对调，一次就修好隔很远的两个值，最少次数常比逆序对少不少。所以每层都得单独当成一道排成升序的最少交换小题。
把一层的值换成名次，交换看环
先用广度优先，拿队列一层层取出节点、凑齐本层的值。对一层，先算出它升序后每个值排第几名，从 0 数起，再把每个位置上的值替成名次。这一换，本层就成了 0 到 k−1 的排列，k 是本层节点数。接着按『谁该去谁的位置』连环：从某位置跳到它的值该去处，再顺着跳，绕回起点成环。长为 L 的环归位刚好要 L−1 次交换——每交换一次至少送一个值回家，最后一个自动落位，故省一次；已在位的值是长度 1 的自环，不用动。整层最少交换就是节点数减环数。
分层取值、逐层结算、层层相加
两层循环。外层用队列做广度优先：每轮先记下队列当前长度，正好是这层的节点数，按它把本层节点依次弹出、收集成值数组，同时把孩子压回队列。内层处理数组：建一张值到名次的映射替换每个元素，再从左到右扫，只要某位置的值名次不等于位置号，就把它跟名次对应位置的值对调，每对调一次答案加一，直到住进正确的值。一层处理完把交换数累加进总答案，队列空了就是结果。
三层挨个算，0 次加 1 次加 2 次
第 0 层只有 45，一个数天然有序，0 次。第 1 层是 80、30，升序里 30 排第 0、80 排第 1，位置上的名次是 1、0；位置 0 住着名次 1、不该在这，和名次 1 的位置对调后换来名次 0 归位，位置 1 正好也是名次 1，一共 1 次。第 2 层是 50、70、20、90，名次依次 1、2、0、3；从位置 0 出发，它住名次 1、和位置 1 对调后住进名次 2，再和位置 2 对调后住进名次 0 归位，位置 1、2、3 都已就位，用了 2 次。三层相加得 3，正是题面给的答案。
单节点层免算，最宽层定复杂度
时间 O(n log n)：每层开销主要在给本层的值排序求名次，一层 k 个节点是 O(k log k)，各层的 k 相加等于总节点数 n，排序项加起来不超过 O(n log n)；建映射和环排序都是每层线性的。空间 O(n)：队列在最宽那层要装下整层节点，再加值数组和名次映射，峰值与节点总数同阶。边界也直接：只有一个节点的层，或本就升序的层，像 [1,2,3,4,5,6] 那样每层都递增，交换都是 0；某层只有两个节点且大的在前，一次对调就修好。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:一层的最少交换次数,等于本层节点数减去环的个数。落到代码里就是把每层的值换算成名次,再用环排序数交换。下面从第 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题