C++에서 합이 최소인 트리 레벨을 찾는 프로그램

<시간/>

이진 트리가 있고 루트의 수준이 1이고 자식의 수준이 2 등이라고 가정합니다. 수준 X에 있는 노드의 모든 값의 합이 최소가 되도록 가장 작은 수준 X를 찾아야 합니다. 트리가 다음과 같다면 -

합이 최소값인 4 – 10 =-6이므로 출력은 2가 됩니다.

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

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

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

예시

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
      right = NULL;
      }
};
class Solution {
   public:
   int solve(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(){
   TreeNode *root = new TreeNode(5);
   root->left = new TreeNode(4);
   root->right = new TreeNode(-10);
   root->left->right = new TreeNode(-2);
   root->right->left = new TreeNode(-7);
   root->right->right = new TreeNode(15);
   Solution ob;
   cout <<ob.solve(root);
}

입력

TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);