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