给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10⁻⁵ 以内的答案可以被接受。

    示例 1：
    输入：root = [3,9,20,null,null,15,7]

    1.       3      
    2.     /   \    
    3.   9       20 
    4.          / \ 
    5.         15  7

    输出：[3.00000,14.50000,11.00000]
    解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
    因此返回 [3, 14.5, 11] 。

    示例 2:
    输入：root = [3,9,20,15,7]

    1.       3      
    2.     /   \    
    3.   9       20 
    4.  / \         
    5. 15  7

    输出：[3.00000,14.50000,11.00000]
    �
    二叉树的层次遍历算法：

    1. public ArrayList<Integer> levelOrder(TreeNode root) {
    2.     ArrayList<Integer> result = new ArrayList<>();
    3.     if (root == null) {
    4.         return result;
    5.     }
    6.     Queue<TreeNode> queue = new LinkedList<>();
    7.     // 将 root 节点放入队列
    8.     queue.offer(root);
    9.     while (!queue.isEmpty()) {
    10.         // 弹出队首元素
    11.         TreeNode node = queue.poll();
    12.         if (node.left != null) {
    13.             // 放入弹出的队首元素的左子节点
    14.             queue.offer(node.left);
    15.         }
    16.         if (node.right != null) {
    17.             // 放入弹出的队首元素的右子节点
    18.             queue.offer(node.right);
    19.         }
    20.         result.add(node.val);
    21.     }
    22.     return result;
    23. }

    标准的层次遍历算法，每次循环只处理了一个元素，那么是否可以每次循环把一层的元素都处理了呢？

    1. public ArrayList<Integer> levelOrder(TreeNode root) {
    2.     ArrayList<Integer> result = new ArrayList<>();
    3.     if (root == null) {
    4.         return result;
    5.     }
    6.     Queue<TreeNode> queue = new LinkedList<>();
    7.     // 将 root 节点放入队列
    8.     queue.offer(root);
    9.     while (!queue.isEmpty()) {
    10.         for (int i = 0; i < ; i++) {
    11.             // 弹出队首元素
    12.             TreeNode node = queue.poll();
    13.             if (node.left != null) {
    14.                 // 放入弹出的队首元素的左子节点
    15.                 queue.offer(node.left);
    16.             }
    17.             if (node.right != null) {
    18.                 // 放入弹出的队首元素的右子节点
    19.                 queue.offer(node.right);
    20.             }
    21.             result.add(node.val);
    22.         }
    23.     }
    24.     return result;
    25. }

    嵌套一层循环，内层循环保证可以循环处理一层的元素，那么内层循环应该循环几次呢？

    观察示例
    637. 二叉树的层平均值 - 图1
    当队列放入节点 3 后，只需要进行1次弹出队首元素的操作就能遍历完第1层的元素
    当队列放入节点 9 和节点 30 后，需要进行2次弹出队首元素的操作才能遍历完第2层的元素
    当队列放入 节点 15 和节点 7 后，需要进行2次弹出队首元素的操作才能遍历完第2层的元素
    可以发现，需要进行弹出队首元素的操作次数即当前队列中的元素个数

    1. public ArrayList<Integer> levelOrder(TreeNode root) {
    2.     ArrayList<Integer> result = new ArrayList<>();
    3.     if (root == null) {
    4.         return result;
    5.     }
    6.     Queue<TreeNode> queue = new LinkedList<>();
    7.     // 将 root 节点放入队列
    8.     queue.offer(root);
    9.     while (!queue.isEmpty()) {
    10.         int size = queue.size();
    11.         for (int i = 0; i < size; i++) {
    12.             // 弹出队首元素
    13.             TreeNode node = queue.poll();
    14.             if (node.left != null) {
    15.                 // 放入弹出的队首元素的左子节点
    16.                 queue.offer(node.left);
    17.             }
    18.             if (node.right != null) {
    19.                 // 放入弹出的队首元素的右子节点
    20.                 queue.offer(node.right);
    21.             }
    22.             result.add(node.val);
    23.         }
    24.     }
    25.     return result;
    26. }

    那么可以在每一层遍历时，累加节点的值，然后除以每一层节点的数量即可得到平均值

    1. public List<Double> averageOfLevels(TreeNode root) {
    2.     return levelOrder(root);
    3. }
    5. public ArrayList<Double> levelOrder(TreeNode root) {
    6.     ArrayList<Double> result = new ArrayList<>();
    7.     if (root == null) {
    8.         return result;
    9.     }
    10.     Queue<TreeNode> queue = new LinkedList<>();
    11.     // 将 root 节点放入队列
    12.     queue.offer(root);
    13.     while (!queue.isEmpty()) {
    14.         double sum = 0;
    15.         int size = queue.size();
    16.         for (int i = 0; i < size; i++) {
    17.             // 弹出队首元素
    18.             TreeNode node = queue.poll();
    19.             if (node.left != null) {
    20.                 // 放入弹出的队首元素的左子节点
    21.                 queue.offer(node.left);
    22.             }
    23.             if (node.right != null) {
    24.                 // 放入弹出的队首元素的右子节点
    25.                 queue.offer(node.right);
    26.             }
    27.             sum = sum + node.val;
    28.         }
    29.         result.add(sum/size);
    30.     }
    31.     return result;
    32. }