C++-এ বাইনারি ট্রি-এ আডজেসেন্ট নোড ছাড়া সর্বোচ্চ সম বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, এমন নোড সাবসেট খুঁজে বের করতে হবে যাতে কোনো দুটি নোড সরাসরি কানেক্টেড (পেরেন্ট-চাইল্ড) নয় এবং তাদের সম সর্বোচ্চ হয়।

সমাধানের পদ্ধতি (DP on Tree + Memoization)

1. প্রতিটি নোডের জন্য دوটি ভ্যালু গণনা করুন:
   • incl = নোড নিলে → নোডের ভ্যালু + পোতা-পোতিদের সর্বোচ্চ সম।
   • excl = নোড নিলে না → চাইল্ডদের সর্বোচ্চ সমের যোগফল।
2. ম্যাপে মেমোইজেশন রাখুন।
3. max(incl, excl) রিটার্ন করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

Node* newNode(int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int getMaxSumUtil(Node* node, map& mp) {
    if (node == NULL) return 0;
    if (mp.find(node) != mp.end()) return mp[node];
    
    int incl = node->data;
    if (node->left) incl += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
    if (node->right) incl += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
    
    int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp);
    
    mp[node] = max(incl, excl);
    return mp[node];
}

int getMaxSum(Node* node) {
    if (node == NULL) return 0;
    map mp;
    return getMaxSumUtil(node, mp);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->right->left = newNode(4);
    root->right->right = newNode(5);
    root->left->left = newNode(1);
    cout << getMaxSum(root) << endl;
    return 0;
}

আউটপুট

11

ব্যাখ্যা

ট্রি: 1(রুট) -> লেফ্ট:2(->লেফ্ট:1), রাইট:3(->লেফ্ট:4, রাইট:5)

সর্বোচ্চ সাবসেট: 1 (রুট) + 4 + 5 + 1 (লেফ্টের লেফ্ট) = 11

জটিলতা

• সময়: O(n)
• স্থান: O(n)