2471. 按层排序二叉树所需的最少操作数

Medium

题目描述

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

解题思路

这个问题可以分解为两个子问题：

层次遍历获取每层节点值：使用 BFS（广度优先搜索）遍历二叉树，将每层的节点值分组存储。
计算每层排序所需的最少交换次数：这是一个经典的数组排序问题。对于一个无序数组，要用最少的交换次数将其排序，可以使用循环分解的方法。

核心思想是：

将数组中的每个元素与其在排序后数组中的正确位置建立映射关系
找出所有的循环（即元素间的置换关系）
对于长度为 k 的循环，需要 k-1 次交换才能排序

具体算法：

对当前层的数组进行排序，得到目标数组
建立值到索引的映射关系
遍历数组，对于每个未访问的位置，找出从该位置开始的循环
对于长度为 k 的循环，累加 k-1 到结果中

时间复杂度为 O(n log n)，主要消耗在排序上；空间复杂度为 O(n)，用于存储层次遍历的队列和临时数组。

代码实现

class Solution {
public:
    int minimumOperations(TreeNode* root) {
        if (!root) return 0;
        
        queue<TreeNode*> q;
        q.push(root);
        int totalSwaps = 0;
        
        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> levelValues;
            
            // 获取当前层的所有值
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                levelValues.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            // 计算当前层排序所需的交换次数
            totalSwaps += getMinSwaps(levelValues);
        }
        
        return totalSwaps;
    }
    
private:
    int getMinSwaps(vector<int>& arr) {
        int n = arr.size();
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());
        
        // 创建值到索引的映射
        unordered_map<int, int> pos;
        for (int i = 0; i < n; i++) {
            pos[arr[i]] = i;
        }
        
        vector<bool> visited(n, false);
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            if (visited[i] || arr[i] == sorted[i]) {
                continue;
            }
            
            // 找循环
            int cycleSize = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = pos[sorted[j]];
                cycleSize++;
            }
            
            if (cycleSize > 1) {
                swaps += cycleSize - 1;
            }
        }
        
        return swaps;
    }
};

class Solution:
    def minimumOperations(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = [root]
        total_swaps = 0
        
        while queue:
            level_size = len(queue)
            level_values = []
            
            # 获取当前层的所有值
            for _ in range(level_size):
                node = queue.pop(0)
                level_values.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # 计算当前层排序所需的交换次数
            total_swaps += self.get_min_swaps(level_values)
        
        return total_swaps
    
    def get_min_swaps(self, arr):
        n = len(arr)
        sorted_arr = sorted(arr)
        
        # 创建值到索引的映射
        pos = {val: i for i, val in enumerate(arr)}
        
        visited = [False] * n
        swaps = 0
        
        for i in range(n):
            if visited[i] or arr[i] == sorted_arr[i]:
                continue
            
            # 找循环
            cycle_size = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = pos[sorted_arr[j]]
                cycle_size += 1
            
            if cycle_size > 1:
                swaps += cycle_size - 1
        
        return swaps

public class Solution {
    public int MinimumOperations(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int totalSwaps = 0;
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            List<int> levelValues = new List<int>();
            
            // 获取当前层的所有值
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                levelValues.Add(node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            // 计算当前层排序所需的交换次数
            totalSwaps += GetMinSwaps(levelValues);
        }
        
        return totalSwaps;
    }
    
    private int GetMinSwaps(List<int> arr) {
        int n = arr.Count;
        List<int> sorted = new List<int>(arr);
        sorted.Sort();
        
        // 创建值到索引的映射
        Dictionary<int, int> pos = new Dictionary<int, int>();
        for (int i = 0; i < n; i++) {
            pos[arr[i]] = i;
        }
        
        bool[] visited = new bool[n];
        int swaps = 0;
        
        for (int i = 0; i < n; i++) {
            if (visited[i] || arr[i] == sorted[i]) {
                continue;
            }
            
            // 找循环
            int cycleSize = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = pos[sorted[j]];
                cycleSize++;
            }
            
            if (cycleSize > 1) {
                swaps += cycleSize - 1;
            }
        }
        
        return swaps;
    }
}

var minimumOperations = function(root) {
    if (!root) return 0;
    
    let totalOps = 0;
    let queue = [root];
    
    while (queue.length > 0) {
        let levelSize = queue.length;
        let levelValues = [];
        
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            levelValues.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        totalOps += minSwapsToSort(levelValues);
    }
    
    return totalOps;
};

function minSwapsToSort(arr) {
    let n = arr.length;
    let indexed = arr.map((val, idx) => [val, idx]);
    indexed.sort((a, b) => a[0] - b[0]);
    
    let visited = new Array(n).fill(false);
    let swaps = 0;
    
    for (let i = 0; i < n; i++) {
        if (visited[i] || indexed[i][1] === i) {
            continue;
        }
        
        let cycleSize = 0;
        let j = i;
        
        while (!visited[j]) {
            visited[j] = true;
            j = indexed[j][1];
            cycleSize++;
        }
        
        if (cycleSize > 1) {
            swaps += cycleSize - 1;
        }
    }
    
    return swaps;
}

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	数值	说明
时间复杂度	O(n log n)	n为二叉树节点总数，主要时间消耗在每层排序上
空间复杂度	O(w)	w为二叉树的最大宽度，用于BFS队列存储

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目