C++의 이진 트리 레벨 평균

비어 있지 않은 이진 트리가 있다고 가정합니다. 반환값에서 각 레벨의 노드 평균값을 배열로 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 [3, 14.5, 11]이 됩니다.

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

• 배열 결과 정의

• 하나의 대기열 정의 q

• 루트를 q에 삽입

• 동안(q가 비어 있지 않음) -

  를 수행합니다.

  • n :=q의 크기

  • 어레이 온도 정의

  • n이 0이 아닌 동안 수행 -

    • t :=q의 첫 번째 요소

    • t의 값을 temp에 삽입

    • q에서 요소 삭제

    • t의 왼쪽이 null이 아닌 경우 -

      • t의 왼쪽을 q에 삽입

    • t의 오른쪽이 null이 아니면 -

      • t의 오른쪽을 q에 삽입

    • (n만큼 1 감소)

  • temp의 크기가 1과 같으면 -

    • 결과 끝에 temp[0] 삽입

  • 그렇지 않으면 temp 크기> 1일 때 -

    • 합계 :=0

    • for initialize i :=0, i

      • 합계 :=합계 + 온도[i]

    • 결과 끝에 (합계 / 임시 크기) 삽입

• 반환 결과

예시

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
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:
   vector<float> averageOfLevels(TreeNode *root){
      vector<float> result;
      queue<TreeNode*> q;
      q.push(root);
      while (!q.empty()) {
         int n = q.size();
         vector<float> temp;
         while (n) {
            TreeNode* t = q.front();
            temp.push_back(t->val);
            q.pop();
            if (t->left && t->left->val != 0)
               q.push(t->left);
            if (t->right && t->right->val != 0)
               q.push(t->right);
               n--;
         }
         if (temp.size() == 1)
            result.push_back(temp[0]);
         else if (temp.size() > 1) {
            double sum = 0;
            for (int i = 0; i < temp.size(); i++) {
               sum += temp[i];
            }
            result.push_back(sum / temp.size());
         }
      }
      return result;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,9,20,NULL,NULL,15,7};
   TreeNode *root = make_tree(v);
   print_vector(ob.averageOfLevels(root));
}

입력

{3,9,20,NULL,NULL,15,7}

출력

[3, 14.5, 11, ]