Giả sử một cây nhị phân được cho. Cây này chứa các nút có giá trị dương và âm. Chúng ta cần tìm tích lớn nhất tại mỗi cấp độ của cây.
Xét cây này, tích của cấp độ 0 là 4, tích của cấp độ 1 là 2 * -5 = -10, và tích của cấp độ 2 là -1 * 3 * -2 * 6 = 36. Đây là tích lớn nhất.
Để giải quyết bài toán này, ta thực hiện duyệt theo cấp độ (level order traversal) của cây. Trong quá trình duyệt, xử lý các nút thuộc các cấp độ riêng biệt. Sau đó lấy tích lớn nhất.
Ví dụ
#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; }Kết quả
Maximum level product is 36