C++中给定二叉树所有层级的非叶子节点的最大和

在这个问题中，我们给定一棵二叉树。我们的任务是创建一个程序，在C++中找到给定二叉树所有层级中非叶子节点的最大和。

问题描述 - 我们将计算树中每一层所有非叶子节点的和，然后打印最大和。

让我们来看一个例子来理解这个问题：

输入 -

输出 - 9

解释 - 每层非叶子节点的和：

Level 1: 4
Level 2: 1+2 = 3
Level 3: 9 (4, 7 are leaf nodes)
Level 4: 0

为了解决这个问题，我们必须进行二叉树的层序遍历，找到所有非叶子节点的和，然后找到它们的 最大和。

因此，在每一层，我们将检查节点是否具有左子节点或右子节点，如果没有，则将其添加到总和中。 并维护一个maxSum变量，它存储到该层为止的最大和。如果所有非叶子节点的和大于maxSum，那么我们将把该层的和初始化为最大值。

示例

程序演示了我们解决方案的实现：

 在线演示

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
int maxLevelSum(struct Node* root){
   if (root == NULL)
      return 0;
   int maxSum = root->data;
   queue<Node*> q;
   q.push(root);
   while (!q.empty()) {
      int count = q.size();
      int levelSum = 0;
      while (count--) {
         Node* temp = q.front();
         q.pop();
         if (temp->left != NULL || temp->right != NULL)
            levelSum = levelSum + temp->data;
         if (temp->left != NULL)
            q.push(temp->left);
         if (temp->right != NULL)
            q.push(temp->right);
      }
      maxSum = max(levelSum, maxSum);
   }
   return maxSum;
}
struct Node* insertNode(int data) {
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main() {
   struct Node* root = insertNode(6);
   root->left = insertNode(1);
   root->right = insertNode(2);
   root->left->left = insertNode(4);
   root->left->right = insertNode(7);
   root->right->right = insertNode(9);
   root->right->right->left = insertNode(5);
   cout<<"The maximum sum of all non-lead nodes at a level of the binary tree is "<<maxLevelSum(root);
   return 0;
}

输出

The maximum sum of all non-lead nodes at a level of the binary tree is 9

更新于：2020年6月3日

129 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告