C++의 이진 트리에서 최대 레벨 합계 찾기

이 문제에서는 양수 값과 음수 값을 가진 이진 트리가 제공됩니다. 우리의 임무는 바이너리 트리에서 최대 레벨 합계를 찾는 것입니다.

문제 설명: 이진 트리가 있고 이진 트리에서 모든 수준의 합을 찾은 다음 최대값을 반환합니다.

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

입력:

<강한>

출력: 5

설명:

레벨 1의 요소 합계:3
수준 2의 요소 합계:-3 + 4 =1
레벨 3의 요소 합계:5 - 1 + 6 - 5 =5

솔루션 접근 방식

문제를 해결하려면 레벨 순서 순회를 사용하여 트리를 순회해야 합니다. 그리고 각 레벨에 대해 합계를 찾은 다음 최대 levelSum을 찾습니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

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

출력

The sum of level with maximum level sum is 5