数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究根据子树权重的差异打印完整二叉树每个节点的更新级别
在这个问题中，我们将根据左右子树的权重差异更新每个子节点的级别。
在这里，我们将递归遍历每个节点的子树以获取左右子树的权重。之后，我们将再次遍历每个子树节点，根据左右子树权重的差异更新其级别。
问题陈述
我们给定一个包含 N 个级别和 2N -1 个节点的完整二叉树。级别从 0 到 N − 1 按降序排列（0、-1、-2、-3 等）。我们需要根据左右子树权重的差异更新每个节点的所有子节点的级别。这里，子树的权重是所有节点值的总和。
将较轻子树的每个节点的级别增加权重差。
将较重子树的每个节点的级别减少权重差。
示例
输入
N = 2 1 / \ 2 3
输出
0, 0, -2
解释
每个节点的初始级别为 [0, -1, -1]。
根节点的级别保持不变。
节点 '1' 的左子树权重为 2，右子树权重为 3。因此，权重差为 1。
当我们将较轻子树的每个节点的级别增加 1 时，节点 2 的级别从 -1 变为 0。
当我们将较重子树的每个节点的级别减少 1 时，节点 3 的级别从 -1 变为 -2。
输入
N = 3
1
/ \
2 3
/ \ / \
4 5 6 7
输出
0, 4, -6, 4, 2, -6, -8
解释
每个节点的初始级别为 [0, -1, -1, -2, -2, -2, -2]。
对于节点 1，左子树的权重为 11，右子树的权重为 16。因此，我们将每个左子树节点的级别增加 5，并将每个右子树节点的级别减少 5。
更新后的级别为 [0, 4, -6, 3, 3, -7, -7]。
对于节点 2，权重差为 1。因此，我们需要更新节点 4 和 5 的级别。
对于节点 3，权重差为 1。因此，我们需要更新节点 6 和 7 的级别。
最终级别为 [0, 4, -6, 4, 2, -6, -8]。
方法
在这种方法中，我们将获取二叉树每个节点的左右子树的权重。之后，我们将根据树是较轻还是较重，根据权重差更新每个子树节点的级别。因为我们有一个完整的二叉树，所以左树总是较轻的，右树总是较重的。
算法
步骤 1 − 定义权重数组并插入二叉树的初始权重。此外，将每个节点的初始级别插入 levels[] 数组中。
步骤 2 − 调用 createCBT() 函数以创建完整的二叉树。
步骤 2.1 − 在 createCBT() 函数中，遍历权重数组并调用 insertNode() 函数以插入给定权重的节点。
步骤 2.1.1 − 在 insertNode() 函数中，创建一个新的 TreeNode。
步骤 2.1.2 − 如果头节点为空，则将新节点分配给头节点。否则，如果队列前端节点的左孩子为空，则插入一个新节点作为左孩子。否则，插入一个新节点作为右孩子，并将前端节点从队列中弹出。
步骤 2.1.3 − 将 newNode 插入队列并返回头节点。
步骤 2.2 − 在每次迭代中更新头节点，并在函数结束时返回它。
步骤 3 − 现在，执行 calcualteLevel() 函数以计算级别。
步骤 3.1 − 如果二叉树为空，则从函数返回。
步骤 3.2 − 执行 getWeight() 函数以获取左右子树的权重。
步骤 3.2.1 − 在 getWeight() 函数中，将当前节点的权重与左子树和右子树的权重相加，并从函数返回它。
步骤 3.3 − 获取权重差。
步骤 3.4 − 调用 updateLevels() 函数以使用权重差更新每个子树节点。
步骤 3.4.1 − 在 updateLevels() 函数中，将权重差添加到当前节点的值，并对左子树和右子树进行递归调用。
步骤 3.5 − 对左子树和右子树进行 calculateLevels() 函数的递归调用。
步骤 4 − 执行 printLevels() 函数以打印所有节点的级别。在 printLevels() 函数中，我们递归遍历完整的二叉树并打印每个节点的更新级别。
示例
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
// To store weight and level
int weight;
int level;
// Left and right pointer
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int wei, int level) {
this->weight = wei;
this->level = level;
left = right = NULL;
}
};
// For inserting a node into a tree
struct TreeNode *insertNode(struct TreeNode *head, int weight, int level, queue<TreeNode *> &que) {
struct TreeNode *new_node = new TreeNode(weight, level);
if (head == NULL)
head = new_node;
// If the left node is empty, insert a new node as a left child
else if (que.front()->left == NULL) {
que.front()->left = new_node;
} else {
// Insert new node as a right child
que.front()->right = new_node;
que.pop();
}
// Insert node into the queue
que.push(new_node);
return head;
}
struct TreeNode *createCBT(vector<int> wei, vector<int> lev) {
struct TreeNode *head = NULL;
// initialize a queue of nodes
queue<TreeNode *> que;
int len = wei.size();
for (int p = 0; p < len; p++) {
// Insert node into the tree
head = insertNode(head, wei[p], lev[p], que);
}
return head;
}
int getWeight(struct TreeNode *head) {
// Weight is 0 for the head node
if (head == NULL)
return 0;
return head->weight + getWeight(head->left) + getWeight(head->right);
}
void updateLevels(struct TreeNode *head, int m) {
if (head == NULL)
return;
// Change the level of the current node
head->level = head->level + m;
// Update the level of each node of the subtree
updateLevels(head->left, m);
updateLevels(head->right, m);
}
void calcualteLevel(struct TreeNode *head) {
if (head == NULL)
return;
int leftWeight = getWeight(head->left);
int rightWeight = getWeight(head->right);
// Get weight difference
int weightDiff = leftWeight - rightWeight;
// Update the levels
updateLevels(head->left, -weightDiff);
updateLevels(head->right, weightDiff);
// Recursive call for subtrees
calcualteLevel(head->left);
calcualteLevel(head->right);
}
void PrintLevels(struct TreeNode *head) {
if (head == NULL)
return;
queue<TreeNode *> que;
que.push(head);
while (!que.empty()) {
cout << que.front()->level << " ";
if (que.front()->left != NULL)
que.push(que.front()->left);
if (que.front()->right != NULL)
que.push(que.front()->right);
que.pop();
}
cout << endl;
}
// Driver code
int main() {
// Number of levels
int N = 3;
int nodes = pow(2, N) - 1;
// Defining the weight of each node
vector<int> weights;
for (int p = 1; p <= nodes; p++) {
weights.push_back(p);
}
vector<int> levels;
// Defining the level of each node
for (int p = 0; p < N; p++) {
for (int q = 0; q < pow(2, p); q++) {
// value of level becomes negative
// While going down the head
levels.push_back(-1 * p);
}
}
// Create a complete binary tree
struct TreeNode *head = createCBT(weights, levels);
calcualteLevel(head);
PrintLevels(head);
return 0;
}
输出
0 4 -6 4 2 -6 -8
时间复杂度 − O(N)
空间复杂度 − O(N)
56 次查看
