এই সমস্যায়, আমাদেরকে ইতিবাচক এবং নেতিবাচক মান সহ একটি বাইনারি ট্রি দেওয়া হয়েছে। আমাদের কাজ হল বাইনারি ট্রিতে সর্বাধিক স্তরের যোগফল খুঁজে বের করা।
সমস্যা বর্ণনা: আমাদের একটি বাইনারি গাছ আছে, আমরা বাইনারি ট্রিতে সমস্ত স্তরের যোগফল খুঁজে বের করব এবং তারপরে তাদের সর্বোচ্চটি ফেরত দেব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
আউটপুট: ৫
ব্যাখ্যা:
লেভেল 1:3 এ উপাদানের যোগফল
লেভেল 2 এ উপাদানের যোগফল:-3 + 4 =1
3 স্তরে উপাদানের যোগফল:5 - 1 + 6 - 5 =5
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের লেভেল অর্ডার ট্রাভার্সাল ব্যবহার করে গাছটি অতিক্রম করতে হবে। এবং প্রতিটি স্তরের জন্য, আমরা যোগফল খুঁজে বের করব এবং তারপর সর্বাধিক স্তরের যোগফল খুঁজে বের করব।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int data){
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
int findMaxLevelSum(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();
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;
}
int main(){
struct Node* root = newNode(3);
root->left = newNode(-3);
root->right = newNode(4);
root->left->left = newNode(5);
root->left->right = newNode(-1);
root->right->left = newNode(6);
root->right->right = newNode(-5);
cout<<"The sum of level with maximum level sum is "<<findMaxLevelSum(root);
return 0;
} আউটপুট
The sum of level with maximum level sum is 5
