इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है जिसमें प्रत्येक नोड का एक मान होता है। हमारा काम बाइनरीट्री में नोड्स की अधिकतम राशि को खोजने के लिए एक प्रोग्राम बनाना है जैसे कि कोई भी दो आसन्न न हो। डायनामिक प्रोग्रामिंग का उपयोग करना।
समस्या का विवरण - हम योग को अधिकतम करने के लिए बाइनरी ट्री के सबसेट को इस तरह से चुनेंगे कि नोड्स सीधे जुड़े न हों।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
आउटपुट
24
स्पष्टीकरण
Elements to be taken under consideration are: 8 + 5 + 9 + 2 = 24
समाधान दृष्टिकोण
समस्या का समाधान मानचित्र का उपयोग करके और नोड्स का योग ज्ञात करना है जैसे कि वे मैक्ससम बनाते हैं। दोनों नोड्स और उनके बच्चे नहीं हो सकते हैं
दी गई शर्त के अनुसार राशि के लिए विचार किया गया। इसलिए, हमें इस तथ्य की जांच करने की आवश्यकता है कि नोड पर विचार करने से पहले, हमें यह जांचना होगा कि क्या इसके चाइल्डट्री में कुछ ऐसे तत्व हैं जो अधिक योग बनाते हैं।
प्रत्येक नोड के लिए एक ही पैरेंट-चाइल्ड सबट्री का योग कई बार खोजने से गणना ओवरहेड बढ़ जाएगी और इससे निपटने के लिए, हम मेमोराइज़ेशन का उपयोग करेंगे और मैक्ससम को एक मैप में नोड तक स्टोर करेंगे जिसे बाद में उपयोग किया जा सकता है।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#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<struct node*, int>& nodeSum);
int sumSubTreeNodes(node* node, map<struct node*, int>& 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<struct node*, int>& 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<struct node*, int> 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