java 解法, 执行用时: 70 ms, 内存消耗: 65.9 MB, 提交时间: 2023-06-13 10:57:50

/**
 * 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) {

        int res = 0;
        // 树为 null 的情况
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> levelList = new ArrayList<>();
            int size  = queue.size();
            
            // 得到该层全部节点
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                levelList.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            
            int loop = 0;
            // 得到该层节点交换次数
            List<Integer> temp = new ArrayList<>(levelList);
            boolean[] flag = new boolean[temp.size()];
            Collections.sort(levelList);
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i=0; i<levelList.size(); i++){
                map.put(levelList.get(i), i);
            }
            for(int i=0; i<temp.size(); i++){
                if(!flag[i]){
                    int j = i;
                    while(!flag[j]){
                        int index = map.get(temp.get(j));
                        flag[j] = true;
                        j = index;
                    }
                    loop++;
                }
            }
            
            res += (temp.size() - loop);
        }
        return res;
    }
}

golang 解法, 执行用时: 192 ms, 内存消耗: 20.1 MB, 提交时间: 2023-06-13 10:57:17

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minimumOperations(root *TreeNode) (ans int) {
	q := []*TreeNode{root}
	for len(q) > 0 {
		n := len(q)
		a := make([]int, n)
		tmp := q
		q = nil
		for i, node := range tmp {
			a[i] = node.Val
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}

		id := make([]int, n) // 离散化后的数组
		for i := range id {
			id[i] = i
		}
		sort.Slice(id, func(i, j int) bool { return a[id[i]] < a[id[j]] })

		ans += n
		vis := make([]bool, n)
		for _, v := range id {
			if !vis[v] {
				for ; !vis[v]; v = id[v] {
					vis[v] = true
				}
				ans--
			}
		}
	}
	return
}

python3 解法, 执行用时: 580 ms, 内存消耗: 55.5 MB, 提交时间: 2023-06-13 10:56:56

# 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
# bfs + 置换环 + 离散化 
class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        ans, q = 0, [root]
        while q:
            a = []
            tmp = q
            q = []
            for node in tmp:
                a.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)

            n = len(a)
            a = sorted(range(n), key=lambda i: a[i])  # 离散化

            ans += n
            vis = [False] * n
            for v in a:
                if vis[v]: continue
                while not vis[v]:
                    vis[v] = True
                    v = a[v]
                ans -= 1
        return ans