इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है जिसमें धनात्मक संख्याएँ होती हैं। हमारा काम C++ में अनुमत आसन्न स्तरों वाले ट्री से अधिकतम योग खोजने के लिए एक प्रोग्राम बनाना है।
कोड विवरण
यहां, हम पेड़ के नोड का अधिकतम योग इस तरह से पाएंगे कि योग में पेड़ के दो आसन्न स्तरों से नोड्स शामिल नहीं हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
आउटपुट
21
स्पष्टीकरण
प्रारंभिक स्तर के रूप में रूट लेना, योग =5 + 3 + 8 + 1 =17 मूल के उप-चाइल्ड को प्रारंभिक स्तर के रूप में लेना, योग =2 + 6 + 9 + 4 =21
समाधान दृष्टिकोण
मैक्ससम को खोजने के लिए, एक शर्त कोई आसन्न तत्व नहीं है। इसके लिए, हम रूट नोड (लेवल 1) से एक योग सेट लेंगे और दूसरा चाइल्ड नोड (लेवल 2) से। पोते-पोतियों के नोड्स को ढूंढकर अगले योग नोड्स को वर्तमान नोड से निकाला जाएगा।
इसके लिए, हम पुनरावर्ती रूप से maxSum मान प्राप्त करेंगे और फिर स्तर 1 या स्तर 2 से शुरू होने वाले योग के लिए अधिकतम योग मान परिणामी maxSum होगा।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#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