इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो c++ में दिए गए बाइनरी ट्री के सभी स्तरों के बीच गैर-पत्ती नोड्स की अधिकतम राशि पायेगा।
समस्या का विवरण - हम पेड़ के सभी गैर-पत्ती नोड्स और प्रत्येक स्तर के योग की गणना करेंगे और फिर अधिकतम योग प्रिंट करेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -
आउटपुट - 9
स्पष्टीकरण - प्रत्येक स्तर पर गैर-पत्ती नोड्स का योग -
Level 1: 4 Level 2: 1+2 = 3 Level 3: 9 (4, 7 are leaf nodes) Level 4: 0
इस समस्या को हल करने के लिए, हमें बाइनरी ट्री का लेवल ऑर्डर ट्रैवर्सल करना होगा और उन सभी नोड्स का योग ज्ञात करना होगा जो नॉन-लीफ नोड्स हैं और फिर उनका अधिकतम योग ज्ञात करें
इसलिए, प्रत्येक स्तर पर, हम जांच करेंगे कि नोड में बाएं या दाएं बच्चे हैं, यदि नहीं, तो इसे योग में जोड़ें। और एक मैक्ससम बनाए रखें जो अधिकतम राशि को स्तर तक संग्रहीत करता है। यदि सभी गैर-पत्ती नोड्स का योग मैक्ससम से अधिक है, तो हम उस स्तर के योग को अधिकतम करने के लिए प्रारंभ करेंगे।
उदाहरण
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,
#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