इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो 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