โปรแกรม C++ หาผลคูณสูงสุดในแต่ละระดับของ Binary Tree

สมมติว่ามี binary tree หนึ่งต้น มีโหนดบวกและลบ เราต้องหาผลคูณสูงสุดในแต่ละระดับของมัน

พิจารณาต้นไม้นี้ ผลคูณของระดับ 0 คือ 4 ผลคูณของระดับ 1 คือ 2 * -5 = -10 และผลคูณของระดับ 2 คือ -1 * 3 * -2 * 6 = 36 นี่คือค่าสูงสุด

เพื่อแก้ปัญหานี้ เราจะทำการท่องระดับ (level order traversal) ของต้นไม้ ระหว่างการท่อง ให้ประมวลผลโหนดของระดับต่างๆ แยกกัน แล้วหาผลคูณสูงสุด

ตัวอย่างโค้ด C++

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