C++의 이진 트리에서 최대 수준 제품 찾기

하나의 이진 트리가 주어진다고 가정합니다. 그것은 긍정적이고 부정적인 노드가 있습니다. 각 수준에서 최대 제품을 찾아야 합니다.

이것이 트리라고 생각하면 수준 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