# Java - BFS & DFS

• BFS:

``````public List<Double> averageOfLevels(TreeNode root) {
while(!q.isEmpty()){
int lvl = q.size();
double sum=0;
for(int i=0; i<lvl; i++) {
if(q.peek().left != null) q.offer(q.peek().left);
if(q.peek().right != null) q.offer(q.peek().right);
sum+=(double)q.poll().val/lvl;
}
}
return ll;
}
``````

DFS: Maintaining Count of Nodes in another List.

``````public List<Double> averageOfLevels(TreeNode root) {
List<Double> al = new ArrayList<>();
List<Integer> count = new ArrayList<>();
traverse(root,0,al,count);
for(int i=0;i<al.size();i++) al.set(i,al.get(i)/count.get(i));
return al;
}

private void traverse(TreeNode node, int lvl, List<Double> al, List<Integer> cnt) {
if(node!=null){
if(al.size()==lvl){
}
else{
cnt.set(lvl, cnt.get(lvl)+1);
al.set(lvl, al.get(lvl)+node.val);
}
traverse(node.left,lvl+1, al, cnt);
traverse(node.right,lvl+1, al, cnt);
}
}``````

• Simple Solution.

``````public List<Double> averageOfLevels(TreeNode root) {
List<long []> list = new ArrayList<>();
helper (root, list, 1);

List<Double> ans = new ArrayList<>();
for (long [] info : list) ans.add (info [0] * 1d/info [1]);
return ans;
}

private void helper (TreeNode node, List<long[]> list, int level) {
if (node == null) return;
if (list.size () < level) list.add (new long [] { 0, 0 });
list.get (level - 1) [0] += node.val;
list.get (level - 1) [1] ++;

helper (node.left, list, level + 1);
helper (node.right, list, level + 1);
}
``````

• This post is deleted!

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