题目

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

  1. Input:
  2.     3
  3.    / \
  4.   9  20
  5.     /  \
  6.    15   7
  7. Output: [3, 14.5, 11]
  8. Explanation:
  9. 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.

题意

计算一个二叉树每一层值的平均值。

思路

层序遍历，注意值越界。

代码实现

Java

  1. class Solution {
  2.     public List<Double> averageOfLevels(TreeNode root) {
  3.         if (root == null) return new ArrayList<>();
  5.         List<Double> ans = new ArrayList<>();
  6.         Queue<TreeNode> q = new LinkedList<>();
  7.         q.offer(root);
  9.         while (!q.isEmpty()) {
  10.             int size = q.size();
  11.             long sum = 0;
  12.             for (int i = 0; i < size; i++) {
  13.                 TreeNode cur = q.poll();
  14.                 sum += cur.val;
  15.                 if (cur.left != null) q.offer(cur.left);
  16.                 if (cur.right != null) q.offer(cur.right);
  17.             }
  18.             ans.add(1.0 * sum / size);
  19.         }
  21.         return ans;
  22.     }
  23. }