C++-এ বাইনারি ট্রিয়ের লেভেল অনুযায়ী গড় (Average of Levels in Binary Tree)

একটি নন-খালি বাইনারি ট্রি দেওয়া আছে। প্রতিটি লেভেলের নোডের গড় মান বের করে অ্যারে আকারে রিটার্ন করতে হবে।

ইনপুট ট্রি (চিত্রে) হলে আউটপুট [3, 14.5, 11]।

সমাধানের ধাপসমূহ

• result অ্যারে সংজ্ঞায়িত করুন
• কিউ q সংজ্ঞায়িত করুন, root পুশ করুন
• যখন q খালি নয়:
  • n := q.size()
  • temp অ্যারে সংজ্ঞায়িত করুন
  • n বার:
    • t := q.front(), temp-এ t.val পুশ করুন, q.pop()
    • t.left ও t.right থাকলে q-তে পুশ করুন
  • temp.size()==1 হলে result-এ temp[0] পুশ করুন
  • অন্যথায় temp-র গড় result-এ পুশ করুন
• result রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; ileft){
            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; ival);
                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;
    }
};
int 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, ]