小红的二叉树排序

[题目链接](https://www.nowcoder.com/practice/7f6dbe10fbe44d6ea8dd1414ed305620)

思路

题目要求：通过交换任意两个节点的权值，用最少的操作次数使二叉树的先序遍历为升序数组。

关键观察

先序遍历得到一个长度为 $n$ 的序列 $a$ ，将其排序后得到目标序列 $b$ 。问题等价于：给定排列 $a$ ，最少交换多少次使其变为 $b$ ？

这是经典的最少交换次数排序问题。

置换环方法

将 $a$ 到 $b$ 的映射看作一个置换（permutation），其中 $a[i]$ 应该被放到 $b$ 中对应的位置。这个置换可以分解为若干个不相交的环（cycle）。

对于一个长度为 $k$ 的环，需要 $k - 1$ 次交换才能让环内所有元素归位。因此，总交换次数为：

$ $\text{ans} = n - \text{环的数量}$ $

样例演示

输入 {1,3,2}，先序遍历得到 $a = [1, 3, 2]$ ，排序后 $b = [1, 2, 3]$ 。

置换关系：

位置 0： $1 \to 1$ （不动）
位置 1： $3$ 应该去位置 2
位置 2： $2$ 应该去位置 1

环： $\{0\}$ ， $\{1 \to 2 \to 1\}$ ，共 2 个环。

答案 $= 3 - 2 = 1$ ，交换位置 1 和位置 2 的值即可。

代码

C++
Java

class Solution {
public:
    void preorder(TreeNode* root, vector<int>& vals) {
        if (!root) return;
        vals.push_back(root->val);
        preorder(root->left, vals);
        preorder(root->right, vals);
    }

    int cntOfSwap(TreeNode* root) {
        vector<int> vals;
        preorder(root, vals);
        int n = vals.size();

        vector<int> sorted_vals(vals.begin(), vals.end());
        sort(sorted_vals.begin(), sorted_vals.end());

        unordered_map<int, int> val_to_idx;
        for (int i = 0; i < n; i++) {
            val_to_idx[sorted_vals[i]] = i;
        }

        vector<int> perm(n);
        for (int i = 0; i < n; i++) {
            perm[i] = val_to_idx[vals[i]];
        }

        vector<bool> visited(n, false);
        int cycles = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            cycles++;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = perm[j];
            }
        }

        return n - cycles;
    }
};

import java.util.*;

public class Solution {
    private void preorder(TreeNode root, List<Integer> vals) {
        if (root == null) return;
        vals.add(root.val);
        preorder(root.left, vals);
        preorder(root.right, vals);
    }

    public int cntOfSwap(TreeNode root) {
        List<Integer> vals = new ArrayList<>();
        preorder(root, vals);
        int n = vals.size();

        int[] sorted = new int[n];
        for (int i = 0; i < n; i++) sorted[i] = vals.get(i);
        Arrays.sort(sorted);

        Map<Integer, Integer> valToIdx = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIdx.put(sorted[i], i);
        }

        int[] perm = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = valToIdx.get(vals.get(i));
        }

        boolean[] visited = new boolean[n];
        int cycles = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            cycles++;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = perm[j];
            }
        }

        return n - cycles;
    }
}

复杂度分析

时间复杂度： $O(n \log n)$ ，其中 $n$ 为二叉树的节点数。先序遍历 $O(n)$ ，排序 $O(n \log n)$ ，计环 $O(n)$ 。
空间复杂度： $O(n)$ 。存储先序序列、排序数组、哈希表和访问标记数组。