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:

1. The range of node's value is in the range of 32-bit signed integer.

给定一颗二叉树，求出二叉树每一层节点的平均值，第一反应是使用二叉树的层次遍历，先回忆一下二叉树的层次遍历

void level_tree(bintree t){      Queue q;      bintree temp;      if(!t){          printf("the tree is empty\n");          return ;      }      q.add(t);      while(!q.isEmpty){          t=poll(q);   //出队        printf("%c ",t.val);          if(t.left != null){               q.add(t.left);        }          if(t.right != null){              q.add(t.right);         }      }  }

 

 

有了模型之后，并不能直接使用，因为这一题要的是每一层的均值，我们需要记录下某一层的节点都有哪些，层次遍历时候，当开始遍历某一层时，队列的大小就是该层的节点数。

public List
      
        averageOfLevels(TreeNode root) {            List < Double > res = new ArrayList < > ();            Queue
       
         q=new LinkedList<>();            q.add(root);            while(!q.isEmpty())            {                int n = q.size();                double sum = 0.0;                for(int i = 0; i