Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

**Example 1:**

Input:3 / \ 9 20 / \ 15 7Output:[3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

**Note:**

- The range of node’s value is in the range of 32-bit signed integer.

## Solution

### BFS Approach

/** * Definition for a binary tree node. * 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) { var list = new List<double>(); Queue<TreeNode> q = new Queue<TreeNode>(); q.Enqueue(root); while(q.Count > 0) { int n = q.Count; double sum = 0.0; for(int i=0;i<n;i++) { TreeNode node = q.Dequeue(); sum += node.val; if(node.left != null) q.Enqueue(node.left); if(node.right != null) q.Enqueue(node.right); } list.Add(sum/n); } return list; } }

**Time Complexity : O(n)**