এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা 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
