637. 二叉树的层平均值
难度简单 238
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入：
3
/
9 20
/
15 7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 , 第 1 层是 14.5 , 第 2 层是 11 。因此返回 [3, 14.5, 11] 。
深度优先搜索
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Integer> counts = new ArrayList<Integer>();
List<Double> sums = new ArrayList<Double>();
dfs(root, 0, counts, sums);
List<Double> averages = new ArrayList<Double>();
int size = sums.size();
for (int i = 0; i < size; i++) {
averages.add(sums.get(i) / counts.get(i));
}
return averages;
}
public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
if (root == null) {
return;
}
if (level < sums.size()) {
sums.set(level, sums.get(level) + root.val);
counts.set(level, counts.get(level) + 1);
} else {
sums.add(1.0 * root.val);//每层进来都走else，右节点dfs时执行if分支。
counts.add(1);
}
dfs(root.left, level + 1, counts, sums); //else
dfs(root.right, level + 1, counts, sums);//if分支
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/
}广度优先搜索
public List<Double> averageOfLevels(TreeNode root) {
List<Double> averages = new ArrayList<Double>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
double sum = 0;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
sum += node.val;
TreeNode left = node.left, right = node.right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
averages.add(sum / size);
}
return averages;
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/
