C++のバイナリツリーで最大レベルの製品を検索します

1つの二分木が与えられたと仮定します。正と負のノードがあります。各レベルで最大の製品を見つける必要があります。

これがツリーであると考えると、レベル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