站外问题水题【23767】

Question

也给我前额叶废物欺负她我饿GIFwig腐恶问他高发期哥特我给他IWC

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用贪心策略。首先，我们需要遍历整个树，找到最深的一层的所有节点，然后从这一层开始，将它们转换成完全二叉树。我们可以通过检查每个节点是否有两个孩子来确定是否为完全二叉树。

以下是实现这个算法的C++代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int minOperations(TreeNode* root) {
    if (root == NULL) return 0;

    vector<int> depths; // 存储每个节点的深度
    queue<TreeNode*> q;
    q.push(root);
    depths.resize(n + 1, -1); // 初始化所有节点的深度为-1，除了根节点设为0
    depths[root->val] = 0;

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (node->left != NULL) {
                depths[node->left->val] = depths[node->val] + 1;
                q.push(node->left);
            }
            if (node->right != NULL) {
                depths[node->right->val] = depths[node->val] + 1;
                q.push(node->right);
            }
        }
    }

    int maxDepth = *max_element(depths.begin(), depths.end());
    int result = 0;

    // 从最深一层开始处理，直到根节点
    for (int depth = maxDepth; depth > 0; --depth) {
        for (auto& node : depths) {
            if (node == depth && (node->left == NULL || node->right == NULL)) {
                if (node->left == NULL) {
                    result++; // 插入左子节点
                } else if (node->right == NULL) {
                    result++; // 插入右子节点
                } else {
                    result += 2; // 删除叶子节点
                }
            }
        }
        depths.erase(remove_if(depths.begin(), depths.end(), [](int d) { return d == depth; }), depths.end());
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> edges(n);
    for (int i = 0; i < n; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }

    // 构建二叉树
    TreeNode* root = new TreeNode(1);
    for (const auto& edge : edges) {
        if (edge.first != 0) {
            TreeNode* parent = root;
            for (int i = 1; i < edge.first; ++i) {
                parent = parent->left ? parent->left : parent->right;
            }
            if (parent->left == NULL) {
                parent->left = new TreeNode(edge.second);
            } else {
                parent->right = new TreeNode(edge.second);
            }
        }
    }

    cout << minOperations(root) << endl;

    // 清理内存
    delete root;
    return 0;
}

这段代码首先构建了给定的二叉树，然后计算每个节点的深度，并根据这些信息计算所需的最小操作次数。注意，这里假设输入的二叉树是有效的，即对于每个非叶子节点，其左子节点编号小于其右子节点编号，且所有节点编号都是唯一的。如果这些假设不成立，你需要在构建二叉树之前添加一些额外的错误检查。