C++ 根据子树权重差异打印完全二叉树中每个节点的更新级别

在这个问题中，我们将根据左右子树的权重差异来更新每个子节点的级别。

在这里，我们将递归地遍历每个节点的子树，以获取左右子树的权重。之后，我们将再次遍历每个子树节点，根据左右子树的权重差来更新其级别。

问题陈述

我们已经给定了一个包含N级和2N-1个节点的完全二叉树。级别从0到N-1按降序编号(0，-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 −如果头节点为null，则将新节点赋给头节点。否则，如果队列前节点的左子节点为null，则将新节点插入为左子节点。否则，将新节点插入为右子节点，并将队列的前节点弹出。
步骤2.1.3 −将newNode插入队列中并返回头节点。
步骤2.2 −在每次迭代中更新头节点，并在函数末尾返回它。
步骤3 −现在，执行calcualteLevel()函数来计算层级。
步骤3.1 −如果二叉树为null，则从函数中返回。
步骤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;
}