ধরুন আমাদের একটি খালি বাইনারি ট্রি নেই; আমাদের প্রতিটি স্তরে নোডের গড় মান খুঁজে বের করতে হবে এবং একটি অ্যারে হিসাবে গড় মান ফেরত দিতে হবে।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে [3, 14.5, 11]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারের ফলাফল সংজ্ঞায়িত করুন
-
একটি সারি q
সংজ্ঞায়িত করুন -
q
-এ রুট সন্নিবেশ করান -
যখন (q খালি নয়), −
করুন-
n :=q এর আকার
-
একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
-
যখন n অ-শূন্য, কর −
-
t :=q
এর প্রথম উপাদান -
temp
-এ t-এর মান সন্নিবেশ করান -
q
থেকে উপাদান মুছুন -
যদি t-এর বামে শূন্য না হয়, তাহলে −
-
q
-এ t-এর বাঁদিকে সন্নিবেশ করান
-
-
যদি t এর ডান শূন্য না হয়, তাহলে −
-
q
-এ t-এর ডানদিকে সন্নিবেশ করান
-
-
(1 দ্বারা n হ্রাস করুন)
-
-
যদি তাপমাত্রার আকার 1 এর মতো হয়, তাহলে -
-
ফলাফলের শেষে temp[0] ঢোকান
-
-
অন্যথায় যখন তাপমাত্রা> 1 এর আকার, তারপর −
-
যোগফল :=0
-
আরম্ভ করার জন্য 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, ]
