इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में दिए गए बाइनरी ट्री के सभी स्तरों पर गैर-पत्ती नोड्स (non-leaf nodes) का अधिकतम योग ढूंढे।
समस्या विवरण - हम ट्री के हर स्तर पर सभी गैर-पत्ती नोड्स का योग निकालेंगे और फिर अधिकतम योग प्रिंट करेंगे।
आइए एक उदाहरण से समझते हैं:
इनपुट -
आउटपुट - 9
व्याख्या - प्रत्येक स्तर पर गैर-पत्ती नोड्स का योग:
स्तर 1: 4 स्तर 2: 1+2 = 3 स्तर 3: 9 (4, 7 पत्ती नोड्स हैं) स्तर 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 << "बाइनरी ट्री के एक स्तर पर सभी गैर-पत्ती नोड्स का अधिकतम योग है " << maxLevelSum(root);
return 0;
}
आउटपुट
बाइनरी ट्री के एक स्तर पर सभी गैर-पत्ती नोड्स का अधिकतम योग है 9
