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

链接：2471.逐层排序二叉树所需的最少操作数目
难度：Medium
标签：树、广度优先搜索、二叉树
简介：返回每一层按 严格递增顺序 排序所需的最少操作数目。

题解 1 - cpp

• 编辑时间：2022-11-13
• 执行用时：324ms
• 内存消耗：144.3MB
• 编程语言：cpp
• 解法介绍：bfs 后遍历每行统计次数。

int m[100005] = {0};
class Solution {
public:
    set<int> s;
    vector<int> list;
    int minimumOperations(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int size = 1, ans = 0;
        while (q.size()) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left) {
                q.push(node->left);
                int val = node->left->val;
                m[val] = list.size();
                list.push_back(val);
                s.insert(val);
            }
            if (node->right) {
                q.push(node->right);
                int val = node->right->val;
                m[val] = list.size();
                list.push_back(val);
                s.insert(val);
            }
            if (--size == 0) {
                ans += check();
                list.clear();
                s.clear();
                size = q.size();
            }
        }
        return ans;
    }
    int check() {
        if (list.empty()) return 0;
        int cnt = 0, idx = 0;
        for (auto &num : s) {
            if (list[idx] != num) {
                cnt++;
                int next = m[num];
                swap(list[idx], list[next]);
                m[list[next]] = next;
                m[num] = idx;
            }
            idx++;
        }
        return cnt;
    }
};