बाइनरी ट्री दिया गया है। ऐसा उपसमुच्चय ढूंढें जिसका योग अधिकतम हो और जिसमें कोई दो नोड्स सीधे जुड़े न हों (पैरेंट-चाइल्ड नहीं)।
उदाहरण ट्री के लिए अधिकतम योग 11 है।
समाधान दृष्टिकोण (मेमोइजेशन के साथ रिकर्सन)
प्रत्येक नोड के लिए दो विकल्प:
- शामिल करें: नोड का मान + पोते-पोतियों का अधिकतम योग।
- बाहर करें: बाएं और दाएं बच्चे के अधिकतम योग का योग।
मैप mp में परिणाम कैश करें।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
struct node *left, *right;
};
struct node* newNode(int data) {
struct node *temp = new struct node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int sumOfGrandChildren(node* node, map& mp);
int getMaxSumUtil(node* node, map& mp);
int sumOfGrandChildren(node* node, map& mp) {
int sum = 0;
if (node->left)
sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp);
if (node->right)
sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp);
return sum;
}
int getMaxSumUtil(node* node, map& mp) {
if (node == NULL) return 0;
if (mp.find(node) != mp.end()) return mp[node];
int incl = node->data + sumOfGrandChildren(node, 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