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

每层各自排成严格递增，最少换几次

给你一棵二叉树，值互不相同。一次操作能挑同一层里的任意两个节点对调它们的值；层数按到根走过的边数算。目标是让每层从左到右严格递增，问最少几次。以题面的 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；某层只有两个节点且大的在前，一次对调就修好。

Python

from __future__ import annotations
from 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 = right
class 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 = 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q{{root}};
        int ans = 0;
        auto f = [](vector<int>& t) {
            int n = t.size();
            vector<int> alls(t.begin(), t.end());
            sort(alls.begin(), alls.end());
            unordered_map<int, int> m;
            int ans = 0;
            for (int i = 0; i < n; ++i) m[alls[i]] = i;
            for (int i = 0; i < n; ++i) t[i] = m[t[i]];
            for (int i = 0; i < n; ++i) {
                while (t[i] != i) {
                    swap(t[i], t[t[i]]);
                    ++ans;
                }
            }
            return ans;
        };
        while (!q.empty()) {
            vector<int> t;
            for (int n = q.size(); n; --n) {
                auto node = q.front();
                q.pop();
                t.emplace_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ans += f(t);
        }
        return ans;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int minimumOperations(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        int ans = 0;
        while (!q.isEmpty()) {
            List<Integer> t = new ArrayList<>();
            for (int n = q.size(); n > 0; --n) {
                TreeNode node = q.poll();
                t.add(node.val);
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            ans += f(t);
        }
        return ans;
    }

    private int f(List<Integer> t) {
        int n = t.size();
        List<Integer> alls = new ArrayList<>(t);
        alls.sort((a, b) -> a - b);
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            m.put(alls.get(i), i);
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = m.get(t.get(i));
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            while (arr[i] != i) {
                swap(arr, i, arr[i]);
                ++ans;
            }
        }
        return ans;
    }

    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}