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.
这个题主要想总结一下bfs算法：
广度优先遍历：类似于树的层序遍历。将根放入队列，一层层遍历，将根弹出后，将左右孩子加入队列。
1、树的广度优先遍历：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public ArrayList bfs(TreeNode root){ ArrayList list=new ArrayList (); if(root==null) return list; Queue queue=new LinkedList (); queue.add(root); while (!queue.isEmpty()){ TreeNode treeNode=queue.poll(); if(treeNode.left!=null) queue.add(treeNode.left); if(treeNode.right!=null) queue.add(treeNode.right); list.add(treeNode.val); } return list; }} 2、图的广度优先遍历
以s为顶点的邻接表为：
S -> A -> B
A -> C -> D
B -> E
class Solution { static HashMap > graph;//输入的邻接表 static HashMap dirt;//距离集合 public static void bfs(HashMap > graph, HashMap dirt,char start){ Queue queue=new LinkedList (); queue.add(start);//把起点加入队列 dirt.put(start,0);//记录每个节点距离顶点的距离 while (!queue.isEmpty()){ char top=queue.poll();//取出队列顶的元素 int d=dirt.get(top)+1; for(Character c:graph.get(top)){ if(!dirt.containsKey(c)){ dirt.put(c,d); queue.add(c); } } } } public static void main(String[] args) { // s顶点的邻接表 LinkedList list_s = new LinkedList (); list_s.add('A'); list_s.add('B'); LinkedList list_a = new LinkedList (); list_a.add('C'); list_a.add('D'); LinkedList list_b = new LinkedList (); list_b.add('D'); list_b.add('E'); LinkedList list_c = new LinkedList (); list_c.add('E'); LinkedList list_d = new LinkedList (); list_c.add('E'); //构造图 graph = new HashMap >(); graph.put('S', list_s); graph.put('A', list_a); graph.put('B', list_b); graph.put('C', list_c); graph.put('D', list_d); graph.put('E', new LinkedList ()); //调用 dirt = new HashMap (); bfs(graph, dirt, 'S'); } } 3、本题解法：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List averageOfLevels(TreeNode root) { List result =new ArrayList<>(); if(root==null) return result; Queue queue=new LinkedList (); queue.add(root); while (!queue.isEmpty()){ int cur=queue.size(); double sum=0; for(int i=0;i