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

这道题到底在问什么

输入

root=[45,80,30,50,70,20,90]

输出

3

输入

root=[1,2,3,4,5,6]

输出

0

最优解：一步一步想明白

1. 3记牢这一句:一层的最少交换次数,等于本层节点数减去环的个数。落到代码里就是把每层的值换算成名次,再用环排序数交换。下面从第 0 层开始,一层一层走。
2. 4答案累计 = 0先把整棵树看清楚。层数是按到根走了几条边算的:根 45 在第 0 层;它的两个孩子 80、30 在第 1 层;最底下 50、70、20、90 在第 2 层。同一层内部才能互相交换,跨层不行。所以这题拆成三道互不相干的小题:每一层各自排好,把次数加起来。
3. 5本层: 45第 0 层紫色高亮,只有一个根节点 45。一个数不用比,天生就是升序,一次都不用换。它这层贡献 0。别小看这一步,它提醒我们:节点数是 1 的层永远 0 次。
4. 6本层用 0 次 · 累计 0这一层就一个 45,已经有序,变绿表示排好了,本层交换 0 次,累计答案还是 0。收工,进下一层。
5. 7本层: 80, 30把第 1 层紫色高亮起来,从左到右是 80、30。目标是把它排成升序 30、80。同一层的值可以任意两两交换,现在的问题就变成:最少换几次能从当前顺序变成升序。
6. 8名次序列: 1, 0关键一步:把每个值换成它在升序里排第几,从 0 数起。80 是第 1 名,30 是第 0 名。于是这一层的位置序列就变成名次 1、0。排好序的样子,就是名次从左到右正好是 0、1,顺次排开。
7. 9位置 0 值 80 名次 1 不在家轮到位置 0,紫色点亮它。它现在住着 80,这个值的名次是 1,不等于位置号 0,说明它坐错了地方。那就动手,把它送回名次 1 对应的位置去。
8. 10换位置 0 和位置 1 · 累计 1看位置 0,它现在住着 80,这个值的名次是 1,该去位置 1。那就直接把位置 0 和位置 1 的值对换,红色标出这两个正在交换的节点。换完位置 1 住进了 80,名次刚好是 1,它安家了。位置 0 又换来 30,还得继续看它归不归位。这一层已经换了 1 次,累计答案到 1。
9. 11位置 0 住进 30(名次 0)换到现在,位置 0 住的值是 30,名次 0,终于等于位置号了,这一整条环理顺了。位置 0 变绿归位。这就是环排序的节奏:盯住一个位置,把不属于它的值一步步顶回各自的家,顺手也把沿途的位置都安顿好。
10. 12位置 1 值 80 名次 1 已在家轮到位置 1。它现在住的值是 80,名次是 1,正好等于位置号 1,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
11. 13本层 1 次 · 累计 1第 1 层全部变绿,从左到右是 30、80,严格递增排好了。这一层一共换了 1 次。回头验证那条结论:本层 2 个节点,拆成了 1 个环,2 减 1 正好是 1,对得上。累计答案现在是 1。
12. 14本层: 50, 70, 20, 90把第 2 层紫色高亮起来,从左到右是 50、70、20、90。目标是把它排成升序 20、50、70、90。同一层的值可以任意两两交换,现在的问题就变成:最少换几次能从当前顺序变成升序。
13. 15名次序列: 1, 2, 0, 3关键一步:把每个值换成它在升序里排第几,从 0 数起。50 是第 1 名,70 是第 2 名,20 是第 0 名,90 是第 3 名。于是这一层的位置序列就变成名次 1、2、0、3。排好序的样子,就是名次从左到右正好是 0、1、2、3,顺次排开。
14. 16位置 0 值 50 名次 1 不在家轮到位置 0,紫色点亮它。它现在住着 50,这个值的名次是 1,不等于位置号 0,说明它坐错了地方。那就动手,把它送回名次 1 对应的位置去。
15. 17换位置 0 和位置 1 · 累计 2看位置 0,它现在住着 50,这个值的名次是 1,该去位置 1。那就直接把位置 0 和位置 1 的值对换,红色标出这两个正在交换的节点。换完位置 1 住进了 50,名次刚好是 1,它安家了。位置 0 又换来 70,还得继续看它归不归位。这一层已经换了 1 次,累计答案到 2。
16. 18换位置 0 和位置 2 · 累计 3看位置 0,它现在住着 70,这个值的名次是 2,该去位置 2。那就直接把位置 0 和位置 2 的值对换,红色标出这两个正在交换的节点。换完位置 2 住进了 70,名次刚好是 2,它安家了。位置 0 又换来 20,还得继续看它归不归位。这一层已经换了 2 次,累计答案到 3。
17. 19位置 0 住进 20(名次 0)换到现在,位置 0 住的值是 20,名次 0,终于等于位置号了,这一整条环理顺了。位置 0 变绿归位。这就是环排序的节奏:盯住一个位置,把不属于它的值一步步顶回各自的家,顺手也把沿途的位置都安顿好。
18. 20位置 1 值 50 名次 1 已在家轮到位置 1。它现在住的值是 50,名次是 1,正好等于位置号 1,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
19. 21位置 2 值 70 名次 2 已在家轮到位置 2。它现在住的值是 70,名次是 2,正好等于位置号 2,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
20. 22位置 3 值 90 名次 3 已在家轮到位置 3。它现在住的值是 90,名次是 3,正好等于位置号 3,说明它本来就在自己家里,一次都不用动,变绿跳过。名次等于位置号的,都是这种省心的自环。
21. 23本层 2 次 · 累计 3第 2 层全部变绿,从左到右是 20、50、70、90,严格递增排好了。这一层一共换了 2 次。回头验证那条结论:本层 4 个节点,拆成了 2 个环,4 减 2 正好是 2,对得上。累计答案现在是 3。
22. 24第 2 层: 一个 3 环加一个自环把第 2 层单独拎出来品一品。它的名次序列本来是 1、2、0、3。跟着箭头走:位置 0 想去 1,位置 1 想去 2,位置 2 又指回 0,这三个位置转成一个长度 3 的大环;位置 3 的名次就是 3,自己指自己,是个长度 1 的自环。一个长度 k 的环,理顺它要 k 减 1 次交换;所以 3 环花 2 次、自环花 0 次,合起来 2 次。节点数减环数,就是这么来的。
23. 25答案 = 3三层全部排好,回放一遍总账:第 0 层单节点 0 次,第 1 层 80 和 30 对换 1 次,第 2 层理顺那个 3 环用了 2 次。零加一加二,一共 3 次,跟开头说的 3 完全对上。整道题就是广度优先分层,每层名次映射再环排序,把各层次数加起来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问