1#include <iostream>
2#include <queue>
3#include <vector>
4using namespace std;
5
6struct TreeNode {
7    int val;
8    TreeNode *left;
9    TreeNode *right;
10    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11};
12
13vector<double> averageOfLevels(TreeNode* root) {
14    vector<double> averages;
15    if (!root) return averages;
16    queue<TreeNode*> q;
17    q.push(root);
18    while (!q.empty()) {
19        long sum = 0, count = 0;
20        queue<TreeNode*> temp;
21        while (!q.empty()) {
22            TreeNode* node = q.front();
23            q.pop();
24            sum += node->val;
25            count++;
26            if (node->left) temp.push(node->left);
27            if (node->right) temp.push(node->right);
28        }
29        averages.push_back((double)sum / count);
30        swap(q, temp);
31    }
32    return averages;
33}
34
35int main() {
36    /* Create Binary tree with nodes */
37    TreeNode a(3), b(9), c(20), d(15), e(7);
38    a.left = &b;
39    a.right = &c;
40    c.left = &d;
41    c.right = &e;
42    
43    vector<double> result = averageOfLevels(&a);
44    for (double avg : result) {
45        cout << avg << " ";
46    }
47    return 0;
48}