สมมุติว่าให้ต้นไม้ไบนารีหนึ่งต้น มีโหนดบวกและลบ เราต้องหาสินค้าให้ได้มากที่สุดในแต่ละระดับของมัน
พิจารณาว่านี่คือต้นไม้ ผลคูณของระดับ 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
