Tìm sản phẩm cấp tối đa trong Cây nhị phân trong C ++

Giả sử, một cây nhị phân được đưa ra. Nó có các nút tích cực và tiêu cực. Chúng ta phải tìm ra sản phẩm tối đa ở mỗi cấp độ của nó.

Coi đây là cái cây nên 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. Vậy đây là tối đa một.

Để giải quyết vấn đề này, chúng ta sẽ thực hiện việc duyệt theo thứ tự mức của cây, trong quá trình duyệt, thực hiện các nút của các mức khác nhau một cách riêng biệt. Sau đó, có được sản phẩm tối đa.

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;
}

Đầu ra

Maximum level product is 36