इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें सकारात्मक और नकारात्मक मान हैं। हमारा कार्य बाइनरी ट्री में अधिकतम स्तर योग खोजना है।
समस्या विवरण: हमारे पास एक बाइनरी ट्री है, हम बाइनरी ट्री में सभी स्तरों का योग खोजेंगे और फिर उनमें से अधिकतम लौटाएंगे।
एक उदाहरण लेकर समस्या को समझते हैं,
इनपुट:
आउटपुट: 5
व्याख्या:
स्तर 1 पर तत्वों का योग: 3
स्तर 2 पर तत्वों का योग: -3 + 4 = 1
स्तर 3 पर तत्वों का योग: 5 - 1 + 6 - 5 = 5
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें लेवल ऑर्डर ट्रैवर्सल का उपयोग करके ट्री को ट्रैवर्स करना होगा। और प्रत्येक स्तर के लिए, हम योग खोजेंगे और फिर अधिकतम levelSum खोजेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
