637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10⁻⁵ 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
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]
3
/ \
9 20
/ \
15 7
输出：[3.00000,14.50000,11.00000]
标准二叉树的层次遍历算法：
public ArrayList<Integer> levelOrder(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();// 将 root 节点放入队列queue.offer(root);while (!queue.isEmpty()) {// 弹出队首元素TreeNode node = queue.poll();if (node.left != null) {// 放入弹出的队首元素的左子节点queue.offer(node.left);}if (node.right != null) {// 放入弹出的队首元素的右子节点queue.offer(node.right);}result.add(node.val);}return result;}
标准的层次遍历算法，每次循环只处理了一个元素，那么是否可以每次循环把一层的元素都处理了呢？
public ArrayList<Integer> levelOrder(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();// 将 root 节点放入队列queue.offer(root);while (!queue.isEmpty()) {for (int i = 0; i < ; i++) {// 弹出队首元素TreeNode node = queue.poll();if (node.left != null) {// 放入弹出的队首元素的左子节点queue.offer(node.left);}if (node.right != null) {// 放入弹出的队首元素的右子节点queue.offer(node.right);}result.add(node.val);}}return result;}
嵌套一层循环，内层循环保证可以循环处理一层的元素，那么内层循环应该循环几次呢？
当队列放入节点 3 后，只需要进行1次弹出队首元素的操作就能遍历完第1层的元素
当队列放入节点 9 和节点 30 后，需要进行2次弹出队首元素的操作才能遍历完第2层的元素
当队列放入 节点 15 和节点 7 后，需要进行2次弹出队首元素的操作才能遍历完第2层的元素
可以发现，需要进行弹出队首元素的操作次数即当前队列中的元素个数
public ArrayList<Integer> levelOrder(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();// 将 root 节点放入队列queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {// 弹出队首元素TreeNode node = queue.poll();if (node.left != null) {// 放入弹出的队首元素的左子节点queue.offer(node.left);}if (node.right != null) {// 放入弹出的队首元素的右子节点queue.offer(node.right);}result.add(node.val);}}return result;}
那么可以在每一层遍历时，累加节点的值，然后除以每一层节点的数量即可得到平均值
public List<Double> averageOfLevels(TreeNode root) {return levelOrder(root);}public ArrayList<Double> levelOrder(TreeNode root) {ArrayList<Double> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();// 将 root 节点放入队列queue.offer(root);while (!queue.isEmpty()) {double sum = 0;int size = queue.size();for (int i = 0; i < size; i++) {// 弹出队首元素TreeNode node = queue.poll();if (node.left != null) {// 放入弹出的队首元素的左子节点queue.offer(node.left);}if (node.right != null) {// 放入弹出的队首元素的右子节点queue.offer(node.right);}sum = sum + node.val;}result.add(sum/size);}return result;}