এই সমস্যাতে, আমাদের একটি বাইনারি ট্রি দেওয়া আছে যাতে ধনাত্মক সংখ্যাগুলো থাকে। আমাদের কাজ হল C++-এ একটি প্রোগ্রাম তৈরি করা যাতে ট্রি থেকে এমন উপাদানগুলোর সর্বোচ্চ যোগফল বের করা যায় যাতে কোনো দুটি আঁচবিক লেভেল (adjacent levels) থেকে উপাদান নেওয়া হয় না।
কোড বিবরণ
এখানে আমরা ট্রির নোডগুলোর সর্বোচ্চ যোগফল বের করব যাতে যোগফলে কোনো দুটি আঁচবিক লেভেলের নোড না থাকে।
উদাহরণ
আউটপুট
21
ব্যাখ্যা
- রুটকে শুরুয়ের লেভেল ধরে: যোগফল = 5 + 3 + 8 + 1 = 17
- রুটের চাইল্ডকে শুরুয়ের লেভেল ধরে: যোগফল = 2 + 6 + 9 + 4 = 21
সমাধানের পদ্ধতি
সর্বোচ্চ যোগফল বের করতে, একটা শর্ত হল আঁচবিক উপাদান নেওয়া যাবে না। এর জন্য আমরা দুটি যোগফল সেট বিবেচনা করব: একটি রুট নোড (লেভেল 1) থেকে এবং অন্যটি চাইল্ড নোড (লেভেল 2) থেকে। পরবর্তী যোগফলের নোডগুলো বর্তমান নোডের গ্র্যান্ডচাইল্ড নোড থেকে বের করা হবে।
রিকার্সিভভাবে সর্বোচ্চ যোগফল বের করলে, লেভেল 1 বা লেভেল 2 থেকে শুরু হওয়া যোগফলের মধ্যে সর্বোচ্চটিই ফলাফল হবে।
প্রোগ্রাম উদাহরণ
#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
