এই সমস্যায়, আমাদেরকে ধনাত্মক সংখ্যা সমন্বিত একটি বাইনারি ট্রি দেওয়া হয়েছে। আমাদের কাজ হল C++ এ অনুমোদিত নয় এমন পার্শ্ববর্তী স্তর সহ একটি গাছ থেকে সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
কোড বর্ণনা
এখানে, আমরা গাছের নোডের সর্বাধিক যোগফল এমনভাবে খুঁজে পাব যাতে যোগফল গাছের দুটি সন্নিহিত স্তরের নোড ধারণ করে না।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
আউটপুট
21
ব্যাখ্যা
রুটকে প্রারম্ভিক স্তর হিসাবে গ্রহণ করা, যোগফল =5 + 3 + 8 + 1 =17 মূলের উপ-চাইল্ডকে প্রারম্ভিক স্তর হিসাবে নেওয়া, যোগফল =2 + 6 + 9 + 4 =21
সমাধান পদ্ধতি
maxSum খুঁজে পেতে, একটি শর্ত হল কোন সংলগ্ন উপাদান নেই। এর জন্য, আমরা রুট নোড (লেভেল 1) থেকে একটি সমষ্টি এবং চাইল্ড নোড (লেভেল 2) থেকে অন্যটি নিব। পরবর্তী সমষ্টি নোডগুলি বর্তমান নোড থেকে নাতি-নাতনি নোডগুলি খুঁজে বের করে বের করা হবে৷
এর জন্য, আমরা পুনরাবৃত্তভাবে maxSum মান খুঁজে বের করব এবং তারপর স্তর 1 বা লেভেল 2 থেকে শুরু হওয়া যোগফলের জন্য সর্বাধিক যোগফলের মান হবে ফলস্বরূপ maxSum৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left, *right;
Node(int item){
data = item;
}
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
if (root == NULL)
return 0;
int sum = root->data;
if (root->left != NULL){
sum += getMaxSum(root->left->left);
sum += getMaxSum(root->left->right);
}
if (root->right != NULL){
sum += getMaxSum(root->right->left);
sum += getMaxSum(root->right->right);
}
return sum;
}
int getMaxSum(Node* root){
if (root == NULL)
return 0;
return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
Node* root = new Node(5);
root->left = new Node(2);
root->right = new Node(10);
root->left->left = new Node(4);
root->left->right = new Node(6);
root->right->right = new Node(9);
cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
return 0;
} আউটপুট
The maximum sum from a tree with adjacent levels not allowed is 24
