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}

using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<double> AverageOfLevels(TreeNode root) {
        List<long> sums = new List<long>();
        List<int> counts = new List<int>();
        dfs(root, 0, sums, counts);
        List<double> averages = new List<double>();
        for (int i = 0; i < sums.Count; i++) {
            averages.Add((double)sums[i] / counts[i]);
        }
        return averages;
    }
    
    private void dfs(TreeNode node, int level, List<long> sums, List<int> counts) {
        if (node == null) return;
        if (level == sums.Count) {
            sums.Add(node.val);
            counts.Add(1);
        } else {
            sums[level] += node.val;
            counts[level]++;
        }
        dfs(node.left, level + 1, sums, counts);
        dfs(node.right, level + 1, sums, counts);
    }
    
    public static void Main(string[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(9);
        TreeNode c = new TreeNode(20);
        TreeNode d = new TreeNode(15);
        TreeNode e = new TreeNode(7);
        a.left = b;
        a.right = c;
        c.left = d;
        c.right = e;
        
        Solution solution = new Solution();
        IList<double> result = solution.AverageOfLevels(a);
        foreach (double avg in result) {
            Console.Write(avg + " ");
        }
    }
}