6235. 逐层排序二叉树所需的最少操作数目

插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。
坚持不懈，越努力越幸运，大家一起学习鸭~~~

题目：

给你一个 值互不相同 的二叉树的根节点 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, 10^5] 。
• 1 <= Node.val <= 10^5
• 树中的所有值 互不相同 。

思路：

先进行树的层次遍历，再看每一层需要交换的次数。 交换次数的计算可以用一个排好序的数组ordered和一个map. map记录原始树层次上的数的位置。

java代码：

/**
 * 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 Solution {
    public int minimumOperations(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int res = 0;
        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int[] temp = new int[size];
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp[i] = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += exchangeTime(temp);
        }

        return res;

    }

    private int exchangeTime(int[] temp) {
        int size = temp.length;
        if (size <= 1) {
            return 0;
        }

        int[] ordered = new int[size];
        System.arraycopy(temp, 0, ordered, 0, size);
        Arrays.sort(ordered);

        Map map = new HashMap(size);
        for (int i = 0; i < size; i++) {
            map.put(temp[i], i);
        }

        int res = 0;
        for (int i = 0; i < size; i++) {
            if (ordered[i] != temp[i]) {
                res++;
                exchange(temp, map, map.get(ordered[i]), i);
            }
        }
        return res;
    }

    private void exchange(int[] temp, Map map, Integer j, int i) {
        int t = temp[j];
        temp[j] = temp[i];
        temp[i] = t;
        map.put(temp[j], j);
        map.put(temp[i], i);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78