# [LeetCode] 637. Average of Levels in Binary Tree 二叉树的层平均值

2021年09月15日 阅读数：1

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.html

Example 1:java

```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:node

1. The range of node's value is in the range of 32-bit signed integer.

Java:app

```public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();

if(root == null) return result;
while(!q.isEmpty()) {
int n = q.size();
double sum = 0.0;
for(int i = 0; i < n; i++) {
TreeNode node = q.poll();
sum += node.val;
if(node.left != null) q.offer(node.left);
if(node.right != null) q.offer(node.right);
}
}
return result;
}　　```

Java: BFSide

```public List<Double> averageOfLevels(TreeNode root) {
queue.offer(root);
while (!queue.isEmpty()) {
int count = queue.size();
double sum = 0;
for (int i = 0; i < count; i++) {
TreeNode cur = queue.poll();
sum += cur.val;
if (cur.left != null) queue.offer(cur.left);
if (cur.right != null) queue.offer(cur.right);
}
}
return list;
}
```

Java: DFS　　post

```class Node {
double sum;
int count;
Node (double d, int c) {
sum = d;
count = c;
}
}
public List<Double> averageOfLevels(TreeNode root) {
List<Node> temp = new ArrayList<>();
helper(root, temp, 0);
for (int i = 0; i < temp.size(); i++) {
}
return result;
}
public void helper(TreeNode root, List<Node> temp, int level) {
if (root == null) return;
if (level == temp.size()) {
Node node = new Node((double)root.val, 1);
} else {
temp.get(level).sum += root.val;
temp.get(level).count++;
}
helper(root.left, temp, level + 1);
helper(root.right, temp, level + 1);
}　　```

Python:url

```# Time:  O(n)
# Space: O(h)
class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
result = []
q = [root]
while q:
total, count = 0, 0
next_q = []
for n in q:
total += n.val
count += 1
if n.left:
next_q.append(n.left)
if n.right:
next_q.append(n.right)
q = next_q
result.append(float(total) / count)
return result
```

Python:orm

```class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
if root is None:
return []
result, current = [], [root]
while current:
next_level, vals,  = [], 0.0
counts = len(current)
for node in current:
vals += node.val
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
current = next_level
result.append(vals / counts)

return result 　　```

Python: wo

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""

res = []
self.helper([root], res)
return res

def helper(self, q, res):
sm = 0.0
counts = 0
next_level = []
while q:
node = q.pop()
counts += 1
sm += node.val
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
res.append(sm / counts)
if next_level:
self.helper(next_level, res)
```

C++:

```class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
if (!root) return {};
vector<double> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int n = q.size();
double sum = 0;
for (int i = 0; i < n; ++i) {
TreeNode *t = q.front(); q.pop();
sum += t->val;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
res.push_back(sum / n);
}
return res;
}
};
```

C++:

```class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> res, cnt;
helper(root, 0, cnt, res);
for (int i = 0; i < res.size(); ++i) {
res[i] /= cnt[i];
}
return res;
}
void helper(TreeNode* node, int level, vector<double>& cnt, vector<double>& res) {
if (!node) return;
if (res.size() <= level) {
res.push_back(0);
cnt.push_back(0);
}
res[level] += node->val;
++cnt[level];
helper(node->left, level + 1, cnt, res);
helper(node->right, level + 1, cnt, res);
}
};
```

[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历 II

[LeetCode] 199. Binary Tree Right Side View 二叉树的右侧视图