मान लीजिए हमारे पास एक गैर-खाली बाइनरी ट्री है; हमें ट्री में प्रत्येक स्तर पर नोड्स के औसत मान को ढूंढना है और औसत मानों को एक सरणी के रूप में वापस करना है।
इसलिए, यदि इनपुट जैसा है:

तो आउटपुट [3, 14.5, 11] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक सरणी
resultपरिभाषित करें - एक कतार
qपरिभाषित करें rootकोqमें डालेंqखाली नहीं होने तक लूप चलाएं:n := q का आकार- एक सरणी
tempपरिभाषित करें nशून्येतर होने तक लूप चलाएं:t := q का पहला तत्वt का मान temp में डालेंq से तत्व हटाएं- यदि
t का बायां null नहीं है, तो:t के बाएं को q में डालें
- यदि
t का दायां null नहीं है, तो:t के दाएं को q में डालें
n को 1 से घटाएं
- यदि
temp का आकार == 1, तो:temp[0] को result के अंत में डालें
- अन्यथा यदि
temp का आकार > 1, तो:sum := 0i := 0सेtemp का आकार - 1तक लूप चलाएं:sum := sum + temp[i]
(sum / temp का आकार) को result के अंत में डालें
resultवापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#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;
}
};
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, ]