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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class Solution {
private final Map<Integer, Pair> map = new HashMap<>();
public List<Double> averageOfLevels(TreeNode root) {
dfs(root, 0);
List<Double> ans = new LinkedList<>();
for (int key : map.keySet()) {
ans.add(map.get(key).getSum() / map.get(key).getNum());
}
return ans;
}
private void dfs(TreeNode root, int level) {
if (root == null) {
return;
}
if (map.containsKey(level)) {
Pair pair = map.get(level);
pair.setNum(pair.getNum() + 1);
pair.setSum(pair.getSum() + root.val);
} else {
Pair pair = new Pair(root.val, 1);
map.put(level, pair);
}
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
}
class Pair {
private double sum;
private double num;
public double getSum() {
return sum;
}
public void setSum(double sum) {
this.sum = sum;
}
public double getNum() {
return num;
}
public void setNum(double num) {
this.num = num;
}
public Pair(double sum, double num) {
this.sum = sum;
this.num = num;
}
@Override
public String toString() {
return String.format("num:%f,sum:%f", num, sum);
}
}
|
