Tổng tối đa của các nút không phải lá trong số tất cả các cấp của cây nhị phân đã cho trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm tổng số tối đa của các nút không phải lá trong số tất cả các cấp của cây nhị phân đã cho trong c ++.

Mô tả sự cố - chúng tôi sẽ tính tổng của tất cả các nút không phải lá của cây và mọi cấp rồi in ra tổng lớn nhất.

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

Đầu vào -

Đầu ra - 9

Giải thích - tổng các nút không phải lá ở mỗi cấp -

Level 1: 4
Level 2: 1+2 = 3
Level 3: 9 (4, 7 are leaf nodes)
Level 4: 0

Để giải quyết vấn đề này, chúng ta sẽ phải thực hiện duyệt thứ tự cấp của cây nhị phân và tìm tổng của tất cả các nút là các nút không phải là nút và sau đó tìm tổng tối đa của chúng

Vì vậy, ở mỗi mức, chúng ta sẽ kiểm tra xem nút có con bên trái hay bên phải hay không, nếu không có thì cộng nó vào tổng. Và duy trì maxSum lưu trữ tổng tối đa cho đến cấp. Nếu tổng của tất cả các nút không phải lá lớn hơn maxSum, thì chúng tôi sẽ khởi tạo tổng của mức đó là lớn nhất.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
int maxLevelSum(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();
         if (temp->left != NULL || temp->right != NULL)
            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;
}
struct Node* insertNode(int data) {
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main() {
   struct Node* root = insertNode(6);
   root->left = insertNode(1);
   root->right = insertNode(2);
   root->left->left = insertNode(4);
   root->left->right = insertNode(7);
   root->right->right = insertNode(9);
   root->right->right->left = insertNode(5);
   cout<<"The maximum sum of all non-lead nodes at a level of the binary tree is "<<maxLevelSum(root);
   return 0;
}

Đầu ra

The maximum sum of all non-lead nodes at a level of the binary tree is 9