এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা 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
