C++ में बाइनरी ट्री में अधिकतम लेवल उत्पाद ढूंढें

मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें पॉजिटिव और नेगेटिव नोड्स हैं। हमें इसके प्रत्येक लेवल पर अधिकतम उत्पाद ढूंढना है।

इसे ट्री मानें, तो लेवल 0 का उत्पाद 4 है, लेवल 1 का उत्पाद 2 * -5 = -10 है, और लेवल 2 का उत्पाद -1 * 3 * -2 * 6 = 36 है। तो यह अधिकतम है।

इसे हल करने के लिए, हम ट्री का लेवल ऑर्डर ट्रैवर्सल करेंगे, ट्रैवर्सल के दौरान, अलग-अलग लेवल के नोड्स को अलग-अलग प्रोसेस करें। फिर अधिकतम उत्पाद प्राप्त करें।

उदाहरण

#include 
#include 
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 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