मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें सकारात्मक और नकारात्मक नोड्स हैं। हमें इसके प्रत्येक स्तर पर अधिकतम उत्पाद खोजना होगा।
मान लीजिए कि यह पेड़ है, तो स्तर 0 का गुणनफल 4 है, स्तर 1 का गुणनफल 2 * -5 =-10 है, और स्तर 2 का गुणनफल -1 * 3 * -2 * 6 =36 है। तो यह है अधिकतम एक।
इसे हल करने के लिए, हम ट्री के लेवल ऑर्डर ट्रैवर्सल को ट्रैवर्सल के दौरान अलग-अलग स्तरों के नोड्स को अलग-अलग करने की प्रक्रिया करेंगे। फिर अधिकतम उत्पाद प्राप्त करें।
उदाहरण
#include<iostream>
#include<queue>
using namespace std;
class Node {
public:
int data;
Node *left, *right;
};
Node* getNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int getMaxLevelProduct(Node* root) {
if (root == NULL)
return 0;
int res = root->data;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int count = q.size();
int prod = 1;
while (count--) {
Node* temp = q.front();
q.pop();
prod *= temp->data;
if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
}
res = max(prod, res);
}
return res;
}
int main() {
Node* root = getNode(4);
root->left = getNode(2);
root->right = getNode(-5);
root->left->left = getNode(-1);
root->left->right = getNode(3);
root->right->left = getNode(-2);
root->right->right = getNode(6);
cout << "Maximum level product is " << getMaxLevelProduct(root) << endl;
} आउटपुट
Maximum level product is 36