Tìm tổng mức tối đa trong Cây nhị phân trong C ++

Trong bài toán này, chúng ta được đưa ra một Cây nhị phân với các giá trị âm và dương. Nhiệm vụ của chúng ta là Tìm tổng mức tối đa trong Cây nhị phân.

Mô tả sự cố: Chúng ta có một cây nhị phân, chúng ta sẽ tìm tổng của tất cả các cấp trong cây nhị phân và sau đó trả về giá trị tối đa của chúng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào:

Đầu ra: 5

Giải thích:

Tổng các phần tử ở cấp 1:3
Tổng các phần tử ở cấp 2:-3 + 4 =1
Tổng các phần tử ở cấp 3:5 - 1 + 6 - 5 =5

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần duyệt qua cây bằng cách sử dụng duyệt theo thứ tự mức. Và đối với mỗi cấp độ, chúng tôi sẽ tìm tổng và sau đó tìm tổng mức tối đa.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;

struct Node {
   
   int data;
   struct Node *left, *right;
};

struct Node* newNode(int data){
   
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}

int findMaxLevelSum(struct Node* root){
   
   if (root == NULL)
      return 0;

   int maxSum = root->data;
   queue<Node*> q;
   q.push(root);
   while (!q.empty()){

      int count = q.size();
      int levelSum = 0;
      while (count--) {
         
         Node* temp = q.front();
         q.pop();
         levelSum = levelSum + temp->data;
         if (temp->left != NULL)
            q.push(temp->left);
         if (temp->right != NULL)
            q.push(temp->right);
      }
      maxSum = max(levelSum, maxSum);
   }
   return maxSum;
}

int main(){
   
   struct Node* root = newNode(3);
   root->left = newNode(-3);
   root->right = newNode(4);
   root->left->left = newNode(5);
   root->left->right = newNode(-1);
   root->right->left = newNode(6);
   root->right->right = newNode(-5);
   cout<<"The sum of level with maximum level sum is "<<findMaxLevelSum(root);
   return 0;
}

Đầu ra

The sum of level with maximum level sum is 5