बाइनरी ट्री दिया गया है। प्रत्येक पैरेंट नोड और उसके दोनों बच्चों के मानों का योग निकालें, और ऐसे सभी जोड़ों में अधिकतम मान खोजें।
केवल वे नोड्स जिनके दोनों बच्चे मौजूद हैं, उन पर विचार करें।
उदाहरण ट्री के लिए अधिकतम योग 91 (16+67+44 या 15+16+17 आदि)।
C++ कार्यान्वयन
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct Node* newNode(int n) {
struct Node* root = new Node();
root->data = n;
root->left = root->right = NULL;
return root;
}
int maxSum(struct Node* root) {
if (root == NULL) return 0;
int res = maxSum(root->left);
if (root->left != NULL && root->right != NULL) {
int sum = root->data + root->left->data + root->right->data;
res = max(res, sum);
}
return max(res, maxSum(root->right));
}
int main() {
struct Node* root = newNode(15);
root->left = newNode(16);
root->left->left = newNode(8);
root->left->left->left = newNode(55);
root->left->right = newNode(67);
root->left->right->left = newNode(44);
root->right = newNode(17);
root->right->left = newNode(7);
root->right->left->right = newNode(11);
root->right->right = newNode(41);
cout << maxSum(root);
return 0;
}
आउटपुट
91
