ধরা যাক, একটি বাইনারি গাছ দেওয়া হল। এটি ইতিবাচক এবং নেতিবাচক নোড আছে। আমাদের এটির প্রতিটি স্তরে সর্বাধিক পণ্য খুঁজে বের করতে হবে।
বিবেচনা করুন এটি গাছ, সুতরাং স্তর 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
