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