C++에서 이진 트리의 최대 수준 합계

이진 트리의 루트가 있고 루트의 수준이 1이고 자식의 수준이 2인 식이라고 가정합니다. 레벨 X에 있는 노드의 모든 값의 합이 최대가 되도록 가장 작은 레벨 X를 반환해야 합니다. 트리가 다음과 같다면 -

그러면 출력은 2, 레벨 1 합계 =1, 레벨 2 합계는 7 + 0 =7, 레벨 2 합계는 7 + (-8) =-1이므로 최대값은 레벨입니다. 2이므로 출력은 2입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

레벨 :=1, 합계 :=r의 값, ansLevel :=레벨, ansSum :=합계
큐 q를 정의하고 주어진 노드 r을 q에 삽입
q가 비어 있지 않은 동안
- 용량 :=q의 크기
- 레벨을 1 증가, 합계 :=0
- 용량이 0이 아닌 동안
  - node :=q의 전면 노드, q의 노드 삭제
  - 노드의 오른쪽이 유효하면 sum :=sum + 오른쪽 노드의 값, 오른쪽 노드를 q에 삽입
  - 왼쪽 노드가 유효하면 sum :=sum + 왼쪽 노드 값, 왼쪽 노드를 q에 삽입
  - 용량 1 감소
- asSum <합계이면 ansSum :=합계, ansLevel :=수준
반환 레벨

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   int maxLevelSum(TreeNode* r) {
      int level = 1, sum = r->val;
      int ansLevel = level, ansSum = sum;
      queue <TreeNode*> q;
      q.push(r);
      while(!q.empty()){
         int capacity = q.size();
         level++;
         sum = 0;
         while(capacity--){
            TreeNode* node = q.front();
            q.pop();
            if(node->right){
               sum += node->right->val;
               q.push(node->right);
            }
            if(node->left){
               sum += node->left->val;
               q.push(node->left);
            }
         }
         if(ansSum<sum){
            ansSum = sum;
            ansLevel = level;
         }
      }
      return ansLevel;
   }
};
main(){
   vector<int> v = {1,7,0,7,-8,NULL,NULL};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout <<ob.maxLevelSum(root);
}

입력

[1,7,0,7,-8,null,null]