小红拿到了一个二叉树，二叉树共有个节点。小红希望你将所有节点赋值为到的正整数，且没有两个节点的值相等。需要满足：奇数层的权值和与偶数层的权值和之差的绝对值不超过1。 如果有多种赋值方案，请返回任意一种方案。如果无解，请返回空树。 数据范围：。给定的二叉树节点初始权值默认为-1。
区块链毕设网qklbishe.com为您提供问题的解答
小红拿到了一个二叉树，二叉树共有个节点。小红希望你将所有节点赋值为
到
的正整数，且没有两个节点的值相等。需要满足：奇数层的权值和与偶数层的权值和之差的绝对值不超过1。
如果有多种赋值方案，请返回任意一种方案。如果无解，请返回空树。
数据范围：。给定的二叉树节点初始权值默认为-1。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <array>
#include <asm-generic/errno.h>
#include <iostream>
#include <queue>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return TreeNode类
*/
TreeNode* fun(TreeNode* root) {
// write code here
int odd = 0, even = 0;
int count = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
if (count & 1) odd += size;
else even += size;
for (int i = 0; i < size; ++i) {
auto tmp = q.front();
q.pop();
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
}
count++;
}
int n = odd + even;
int sum = n * (n + 1) / 2;
int odd_s = (odd + 1) * odd / 2;
if (odd_s > (sum / 2 + 1)) return nullptr;
array<bool, 100005> arr{false};
for (int i = 1; i <= odd; ++i) arr[i] = true;
int dis = n – odd;
int oddm = 0;
if (odd > even) oddm = (sum + 1) / 2;
else oddm = sum / 2;
oddm -= odd_s;
for (int i = odd; i > 0; —i) {
if (oddm > dis) {
oddm -= dis;
arr[i] = false;
arr[i + dis] = true;
} else {
arr[i] = false;
arr[i + oddm] = true;
oddm = 0;
break;
}
}
if (oddm != 0) return nullptr;
q.push(root);
count = 0;
odd = even = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto tmp = q.front();
q.pop();
if (count & 1) {
while (!arr[odd]) odd++;
tmp->val = odd;
odd++;
} else {
while (arr[even]) even++;
tmp->val = even;
even++;
}
if (tmp->left) q.push(tmp->left);
if (tmp->right) q.push(tmp->right);
}
count++;
}
return root;
}
};
05:15
以上就是关于问题小红拿到了一个二叉树，二叉树共有个节点。小红希望你将所有节点赋值为到的正整数，且没有两个节点的值相等。需要满足：奇数层的权值和与偶数层的权值和之差的绝对值不超过1。
如果有多种赋值方案，请返回任意一种方案。如果无解，请返回空树。
数据范围：。给定的二叉树节点初始权值默认为-1。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
