इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम एक प्रोग्राम बनाना है जो C++ में एक बाइनरी ट्री में अधिकतम सर्पिल योग प्राप्त करेगा।
सर्पिल योग बाइनरी ट्री का, बाइनरी ट्री के स्पाइरल ट्रैवर्सल में पाए जाने वाले नोड्स का योग होता है।
एक पेड़ के सर्पिल ट्रैवर्सल में, नोड्स को रूट से लीफ नोड तक ट्रैवर्स किया जाता है। ट्रैवर्सल बाएं से दाएं और फिर अगले स्तर के लिए दाएं से बाएं और आगे के स्तरों के लिए होता है।
उदाहरण -
आउटपुट -5
स्पष्टीकरण -
हम पेड़ के दूसरे स्तर के पहले नोड तक सर्पिल ट्रैवर्सल पर विचार करेंगे।
1+ 5 = 5.
तीसरी पंक्ति के योग तत्व हैं (1-9+6-4 =-6) जो समग्र योग को कम करेगा, इसलिए अधिकतम योग को देखते हुए इसे हटा दिया जाता है।
इस समस्या को हल करने के लिए, हम एक सरणी का उपयोग करेंगे जो प्रत्येक स्तर पर तत्वों के योग को संग्रहीत करेगा, और प्रत्येक स्तर पर स्पिलर योग खोजने के लिए, हम दो स्टैक का उपयोग करेंगे। फिर अंत में, हम जाँच करेंगे कि क्या स्तर के बाद राशि को शामिल करने से अधिकतम राशि बढ़ जाती है, यदि हाँ तो हम इसे ले लेंगे अन्यथा शेष सर्पिल को त्याग दें।
उदाहरण
बाइनरी ट्री में अधिकतम सर्पिल योग खोजने का कार्यक्रम
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* insertNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int findMaxSum(vector<int> arr, int n){
int sum = INT_MIN;
int maxSum = INT_MIN;
for (int i = 0; i < n; i++) {
if (sum < 0)
sum = arr[i];
else
sum += arr[i];
maxSum = max(maxSum, sum);
}
return maxSum;
}
int SpiralSum(Node* root){
if (root == NULL)
return 0;
stack<Node*> sRtL;
stack<Node*> sLtR;
vector<int> arr;
sRtL.push(root);
while (!sRtL.empty() || !sLtR.empty()) {
while (!sRtL.empty()) {
Node* temp = sRtL.top();
sRtL.pop();
arr.push_back(temp->data);
if (temp->right)
sLtR.push(temp->right);
if (temp->left)
sLtR.push(temp->left);
}
while (!sLtR.empty()) {
Node* temp = sLtR.top();
sLtR.pop();
arr.push_back(temp->data);
if (temp->left)
sRtL.push(temp->left);
if (temp->right)
sRtL.push(temp->right);
}
}
return findMaxSum(arr, arr.size());
}
int main(){
Node* root = insertNode(1);
root->left = insertNode(5);
root->right = insertNode(-1);
root->left->left = insertNode(-4);
root->left->right = insertNode(6);
root->right->left = insertNode(-9);
root->right->right = insertNode(1);
cout << "Maximum Spiral Sum in binary tree : "<<SpiralSum(root);
return 0;
} आउटपुट
Maximum Spiral Sum in binary tree : 6