05 August 2008
给定二叉树的根，以数组的形式返回每一层节点的平均值。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> sum = new ArrayList();
List<Integer> size = new ArrayList();
dfs(root, 0, sum, size);
List<Double> li = new ArrayList<Double>();
for (int i = 0; i < sum.size(); i++) {
li.add(sum.get(i) / size.get(i));
}
return li;
}
private void dfs(TreeNode root, int level, List<Double> sum, List<Integer> size) {
if (root == null) {
return;
}
if (level == sum.size()) {
sum.add(Double.valueOf(root.val));
size.add(1);
} else {
sum.set(level, sum.get(level) + root.val);
size.set(level, size.get(level) + 1);
}
dfs(root.left, level + 1, sum, size);
dfs(root.right, level + 1, sum, size);
}
}
BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return result;
}
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
double sum = 0.0;
for (int i = 0; i <n; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(sum/n);
}
return result;
}
}