Mức trung bình trong cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân không rỗng; chúng ta phải tìm giá trị trung bình của các nút trên mỗi cấp để trả về giá trị trung bình dưới dạng một mảng.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là [3, 14,5, 11].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một kết quả mảng

• Xác định một hàng đợi q

• chèn root vào q

• while (không phải q trống), do -

  • n:=kích thước của q

  • Xác định tạm thời mảng

  • trong khi n khác 0, do -

    • t:=phần tử đầu tiên của q

    • chèn giá trị của t vào tạm thời

    • xóa phần tử khỏi q

    • nếu bên trái của t không rỗng, thì -

      • chèn bên trái của t vào q

    • nếu bên phải của t không rỗng, thì -

      • chèn bên phải của t vào q

    • (giảm n đi 1)

  • nếu kích thước của nhiệt độ bằng 1, thì -

    • chèn tạm thời [0] vào cuối kết quả

  • ngược lại khi kích thước của nhiệt độ> 1, thì -

    • tổng:=0

    • để khởi tạo i:=0, khi tôi

      • sum:=sum + temp [i]

    • insert (sum / size of temp) vào cuối kết quả

• trả về kết quả

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

[3, 14.5, 11, ]