payal-kothari
7/13/2017 - 5:40 PM

Using BFS // refer this code for BFS From https://leetcode.com/problems/average-of-levels-in-binary-tree/#/description

Using BFS

// refer this code for BFS

From https://leetcode.com/problems/average-of-levels-in-binary-tree/#/description

Average of levels in binary tree.java
content_copyfile_download
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
 // BFS   *********
 
public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        
        List<Double> list = new ArrayList<>();             // ***
        Queue<TreeNode> q = new LinkedList<TreeNode>();    // ***
        
        double avg = 0.0;
        q.add(root);
        
        while (!q.isEmpty()){
            
            int n = q.size();
            double sum = 0.0;
            
            for(int i =0 ; i<n ; i++){          // empty complete level of the tree
                TreeNode t = q.poll();
                sum = sum + t.val;
               
                if (t.left != null) { q.add(t.left); }
                
                if (t.right != null) { q.add(t.right); }
                
            }
            
            if (n == 1) {
                list.add(sum); 
            }
            else{
                avg = sum / n;
                list.add(avg);
            }     
        }    
        return list;
        
    }
}