এই সমস্যায় আমাদের একটি বাইনারি ট্রি দেওয়া আছে যাতে পজিটিভ এবং নেগেটিভ মান আছে। আমাদের কাজ বাইনারি ট্রিতে সর্বোচ্চ লেভেল সম বের করা।
সমস্যা বর্ণনা: আমাদের একটি বাইনারি ট্রি আছে, আমরা বাইনারি ট্রির সব লেভেলের যোগফল বের করব এবং তারপর সেগুলোর মধ্যে সর্বোচ্চটি রিটার্ন করব।
উদাহরণ:
ইনপুট:
আউটপুট: 5
ব্যাখ্যা:
লেভেল ১-এ উপাদানগুলোর যোগফল: 3
লেভেল ২-এ উপাদানগুলোর যোগফল: -3 + 4 = 1
লেভেল ৩-এ উপাদানগুলোর যোগফল: 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
