C++에서 주어진 이진 트리의 모든 수준 중 잎이 아닌 노드의 최대 합계

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 C++에서 주어진 이진 트리의 모든 수준 중에서 잎이 아닌 노드의 최대 합을 찾는 프로그램을 만드는 것입니다.

문제 설명 - 우리는 트리의 모든 잎이 아닌 노드와 모든 레벨의 합계를 계산한 다음 최대 합계를 출력합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력 -

출력 − 9

설명 - 각 수준에서 잎이 아닌 노드의 합 -

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

이 문제를 해결하려면 이진 트리의 레벨 순서 순회를 수행하고 잎이 아닌 노드인 모든 노드의 합을 찾은 다음 이들의 최대 합을 찾아야 합니다.

따라서 각 수준에서 노드에 왼쪽 또는 오른쪽 자식이 있는지 확인하고 그렇지 않은 경우 합계에 추가합니다. 그리고 레벨까지 최대 합계를 저장하는 maxSum을 유지하십시오. 리프가 아닌 모든 노드의 합이 maxSum보다 크면 해당 수준의 합을 최대값으로 초기화합니다.

예시

솔루션 구현을 보여주는 프로그램,

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

출력

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