319场周赛 逐层排序二叉树所需的最小操作数目

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

本问题主要由两个部分组成:

  1. 遍历二叉树,找到每一层的子数组(层序遍历)
  2. 排序数组需要的最小交换次数(循环图)

第一次接触到循环图解决数组的最小交换次数。具体思路就是,假设原数组为 2 1 5 3 4,那么排序之后的数组就是1 2 3 4 5。尝试按照排序前后的位置建图,也就是排序后的位置指向其原位置,这样出度入度都是1。
排序后的第一个数1原位置为2,那么就有1 -> 2,排序后第二个数原位置为1,那么就有1 -> 2 ->1,这就是第一个循环图。第二个循环图是3 -> 4 -> 5 ->3。考虑两种情况,一个是交换两个循环图中的元素,比如2和3,3 1 5 2 4,那么循环图就是1 -> 2 -> 4 -> 5 -> 3 -> 1,可以看到两个循环图合并为一个循环图。假设交换同一个循环图中的元素,比如3和4,2 1 5 4 3。第二个循环图就会拆分为3 -> 5 -> 3, 4 -> 4,可以看到交换同一个循环图中的元素会将循环图拆分为两个循环图。
排序的目标就是使得最后有n个循环图,1->1,2->2…..n->n。所以要将所有节点数目大于1的循环图拆分为多个循环图,节点数目为K的循环图需要拆分K-1次,也就是交换K-1次。所以主要是求解所有的循环图并求和(其节点数目-1)。关键是具体如何实现求解循环图,由于是循环的,从i出发,我们可以记录其在原数组中的位置,并不断遍历下去,直到找到一个节点的原数组位置为i,也就是回来了并且是循环的,就结束。

code

/**
 * 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:

    void level_travel(TreeNode * root,vector<vector<int>> &nodes)
    {
        queue<TreeNode*> q;

        q.push(root);
        
        while(!q.empty())
        {
            vector<int> level;
            int len = q.size();
            for(int i = 0;i < len;i ++)
            {
                TreeNode* cur = q.front();
                q.pop();
                level.push_back(cur -> val);
                if(cur -> left != nullptr) q.push(cur -> left);
                if(cur -> right != nullptr) q.push(cur -> right);
            }

            nodes.push_back(level);
        }
    }
    
    int min_swap(vector<int> arr)
    {
        int n = arr.size();

        pair<int,int> arrpos[n];

        //for(int i = 0;i < n;i ++) cout<<arr[i]<<" "; cout<<endl;

        //使用一个pair数组记录下每个元素的原位置
        for(int i = 0;i < n;i ++)
        {
            arrpos[i].first = arr[i];
            arrpos[i].second = i;
        }
        
        sort(arrpos,arrpos + n);

        //记录当前节点是否已经在循环图中
        vector<int> visited(n,0);

        int ans = 0;
        for(int i = 0;i < n;i ++)
        {
            //如果已经在循环图中并且本身就是循环图
            if(visited[i] || arrpos[i].second == i) continue;

            int cycle_size = 0;
            int j = i;
            while(!visited[j])
            {
                visited[j] = 1;
                j = arrpos[j].second;
                cycle_size++;
            }

            if(cycle_size > 0) ans += (cycle_size - 1);
        }

        return ans;
    }
    int minimumOperations(TreeNode* root) {
        vector<vector<int>> nodes;

        level_travel(root,nodes);

        int ans = 0;

        for(int i = 0;i < nodes.size();i ++)
            ans += min_swap(nodes[i]);

        return ans;    
    }
};

原文地址:http://www.cnblogs.com/huangxk23/p/16890043.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性