1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5    public int val;
6    public TreeNode left;
7    public TreeNode right;
8    public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12    public IList<double> AverageOfLevels(TreeNode root) {
13        List<double> averages = new List<double>();
14        Queue<TreeNode> queue = new Queue<TreeNode>();
15        queue.Enqueue(root);
16        while (queue.Count > 0) {
17            int count = queue.Count;
18            double sum = 0;
19            for (int i = 0; i < count; i++) {
20                TreeNode node = queue.Dequeue();
21                sum += node.val;
22                if (node.left != null) queue.Enqueue(node.left);
23                if (node.right != null) queue.Enqueue(node.right);
24            }
25            averages.Add(sum / count);
26        }
27        return averages;
28    }
29    
30    public static void Main(string[] args) {
31        TreeNode a = new TreeNode(3);
32        TreeNode b = new TreeNode(9);
33        TreeNode c = new TreeNode(20);
34        TreeNode d = new TreeNode(15);
35        TreeNode e = new TreeNode(7);
36        a.left = b;
37        a.right = c;
38        c.left = d;
39        c.right = e;
40        
41        Solution solution = new Solution();
42        IList<double> result = solution.AverageOfLevels(a);
43        foreach (double avg in result) {
44            Console.Write(avg + " ");
45        }
46    }
47}