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

**Approach 1: Using Classical BFS**

**Here we used Queue with Poll and Offer function for managing the queue.**

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> result = new ArrayList<>(); Queue<TreeNode> q = new LinkedList<>(); if(root==null)return result; q.offer(root); while (!q.isEmpty()){ double sum=0; int n= q.Size(); for(int i=0;i<n;i++){ TreeNode node= q.poll(); sum+=node.val; if(node.left!=null)q.offer(node.left); if(node.right!=null)q.offer(node.right); } result.add(sum/n); } return result; }