Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output:
[3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node's value is in the range of 32-bit signed integer.
2. Implementation
(1) BFS
public class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
double sum = 0;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.remove();
sum += curNode.val;
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
res.add(sum / size);
}
return res;
}
}
(2) DFS
思路:主要是维护两个数组,分别记录每一层的levelSum, 和对应的size
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) {
return res;
}
int height = getHeight(root);
long[] levelSum = new long[height];
int[] size = new int[height];
getLevelAverage(root, 0, levelSum, size);
for (int i = 0; i < height; i++) {
res.add(levelSum[i] * 1.0 / size[i]);
}
return res;
}
public void getLevelAverage(TreeNode node, int depth, long[] levelSum, int[] size) {
if (node == null) {
return;
}
levelSum[depth] += node.val;
size[depth] += 1;
getLevelAverage(node.left, depth + 1, levelSum, size);
getLevelAverage(node.right, depth + 1, levelSum, size);
}
public int getHeight(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}