하나의 이진 트리가 주어진다고 가정합니다. 그것은 긍정적이고 부정적인 노드가 있습니다. 각 수준에서 최대 제품을 찾아야 합니다.
이것이 트리라고 생각하면 수준 0의 곱은 4이고 수준 1의 곱은 2 * -5 =-10이고 수준 2의 곱은 -1 * 3 * -2 * 6 =36입니다. 따라서 이것은 최대 1개.
이를 해결하기 위해 우리는 트리의 레벨 오더 순회를 수행할 것이며, 순회하는 동안 서로 다른 레벨의 노드를 개별적으로 수행하는 프로세스를 수행할 것입니다. 그런 다음 최대 제품을 얻으십시오.
예
#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