इस समस्या में, हमें एक बाइनरी ट्री दिया गया है जिसमें प्रत्येक नोड का एक मान है। हमारा कार्य एक प्रोग्राम बनाना है जो डायनामिक प्रोग्रामिंग का उपयोग करके बाइनरी ट्री में ऐसे नोड्स का अधिकतम योग ढूंढे जो आसन्न न हों।
समस्या विवरण
हम बाइनरी ट्री के उपसमुच्चय (subsets) को चुनेंगे ताकि योग अधिकतम हो और नोड्स सीधे जुड़े न हों।
उदाहरण
इनपुट
आउटपुट
24
व्याख्या
विचार किए जाने वाले तत्व हैं: 8 + 5 + 9 + 2 = 24
समाधान दृष्टिकोण
समस्या का एक समाधान मैप का उपयोग करके नोड्स का योग ढूंढना है ताकि वे maxSum बनाएं। दिए गए शर्त के अनुसार नोड्स और उनके बच्चे दोनों को योग के लिए नहीं माना जा सकता। इसलिए, हमें इस तथ्य की जांच करनी होगी कि किसी नोड पर विचार करने से पहले, हमें जांचना होगा कि क्या उसके चाइल्ड सबट्री में कुछ तत्व हैं जो अधिक योग बनाते हैं।
प्रत्येक नोड के लिए समान पैरेंट-चाइल्ड सबट्री के योग को कई बार ढूंढने से कम्प्यूटेशन ओवरहेड बढ़ेगा और इससे निपटने के लिए, हम मेमोराइजेशन का उपयोग करेंगे और नोड तक के maxSum को एक मैप में संग्रहीत करेंगे जिसका उपयोग बाद में किया जा सकता है।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#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 findMaxSumBT(node* node, map& nodeSum);
int sumSubTreeNodes(node* node, map& nodeSum){
int maxSum = 0;
if (node->left)
maxSum += findMaxSumBT(node->left->left, nodeSum) +
findMaxSumBT(node->left->right, nodeSum);
if (node->right)
maxSum += findMaxSumBT(node->right->left, nodeSum) +
findMaxSumBT(node->right->right, nodeSum);
return maxSum;
}
int findMaxSumBT(node* node, map& nodeSum){
if (node == NULL)
return 0;
if (nodeSum.find(node) != nodeSum.end())
return nodeSum[node];
int sumInclCurr = node->data + sumSubTreeNodes(node, nodeSum);
int sumExclCurr = findMaxSumBT(node->left, nodeSum) +
findMaxSumBT(node->right, nodeSum);
nodeSum[node] = max(sumInclCurr, sumExclCurr);
return nodeSum[node];
}
int main(){
node* root = newNode(9);
root->left = newNode(4);
root->right = newNode(7);
root->left->left = newNode(8);
root->left->right = newNode(5);
root->right->left = newNode(2);
map nodeSum;
cout<<"Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is "<<findMaxSumBT(root, nodeSum);
return 0;
}
आउटपुट
Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is 24
