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