BFS - Queue


  • 0
    P
    public List<Double> averageOfLevels(TreeNode root) {
            List<Double> list = new ArrayList<>();
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            int lcount = 0;
            long lsum = 0; // we need long here
                    
            while (!q.isEmpty()) {          
                
                int n = q.size();
                
                while (n > 0) {
                    TreeNode elem = q.remove();
                    lsum += elem.val;
    
                    lcount++;
                    n--;
                    
                    if (n == 0) {
                        list.add((lsum*1.0)/lcount);
                        lsum = 0;
                        lcount = 0;
                    }
                
                    if (elem.left != null)
                        q.add(elem.left);
                
                    if (elem.right != null)
                        q.add(elem.right);
                }
            }
            
            return list;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.