637.Average of Levels in Binary Tree
637.Average of Levels in Binary Tree
难度:Easy
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
1
示例 1:
2
3
输入:
4
3
5
/ \
6
9 20
7
/ \
8
15 7
9
输出: [3, 14.5, 11]
10
解释:
11
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
12
注意:
13
14
节点值的范围在32位有符号整数范围内。
Copied!
分层遍历可以使用基本的队列存储,
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
vector<double> averageOfLevels(TreeNode* root) {
13
vector<double>res;
14
if(!root) return res;
15
deque<TreeNode*> tree(1,root);
16
while(!tree.empty())
17
{
18
double sum=0.0;
19
int len=tree.size();
20
int k=len;
21
while(k--)
22
{
23
sum+=tree[0]->val;
24
if(tree[0]->left) tree.push_back(tree[0]->left);
25
if(tree[0]->right) tree.push_back(tree[0]->right);
26
tree.pop_front();
27
}
28
res.push_back(sum/len);
29
30
}
31
return res;
32
33
}
34
};
Copied!
Copy link