categories: [Blog,Algorithm]

637. 二叉树的层平均值

难度简单238
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：
输入：
3
/ \
9 20
/ \
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

深度优先搜索

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public List<Double> averageOfLevels(TreeNode root) {
  12.         List<Integer> counts = new ArrayList<Integer>();
  13.         List<Double> sums = new ArrayList<Double>();
  14.         dfs(root, 0, counts, sums);
  15.         List<Double> averages = new ArrayList<Double>();
  16.         int size = sums.size();
  17.         for (int i = 0; i < size; i++) {
  18.             averages.add(sums.get(i) / counts.get(i));
  19.         }
  20.         return averages;
  21.     }
  23.     public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
  24.         if (root == null) {
  25.             return;
  26.         }
  27.         if (level < sums.size()) {
  28.             sums.set(level, sums.get(level) + root.val);
  29.             counts.set(level, counts.get(level) + 1);
  30.         } else {
  31.             sums.add(1.0 * root.val);//每层进来都走else，右节点dfs时执行if分支。
  32.             counts.add(1);
  33.         }
  34.         dfs(root.left, level + 1, counts, sums); //else
  35.         dfs(root.right, level + 1, counts, sums);//if分支
  36.     }
  37. // 作者：LeetCode-Solution
  38. // 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/
  39. }

广度优先搜索

  1. public List<Double> averageOfLevels(TreeNode root) {
  2.         List<Double> averages = new ArrayList<Double>();
  3.         Queue<TreeNode> queue = new LinkedList<TreeNode>();
  4.         queue.offer(root);
  5.         while (!queue.isEmpty()) {
  6.             double sum = 0;
  7.             int size = queue.size();
  8.             for (int i = 0; i < size; i++) {
  9.                 TreeNode node = queue.poll();
  10.                 sum += node.val;
  11.                 TreeNode left = node.left, right = node.right;
  12.                 if (left != null) {
  13.                     queue.offer(left);
  14.                 }
  15.                 if (right != null) {
  16.                     queue.offer(right);
  17.                 }
  18.             }
  19.             averages.add(sum / size);
  20.         }
  21.         return averages;
  22.     }
  24. 作者：LeetCode-Solution
  25. 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/