( “树” 之 BFS) 637. 二叉树的层平均值 ——【Leetcode每日一题】
637. 二叉树的层平均值
给定一个非空二叉树的根节点 root
, 以数组的形式返回每一层节点的平均值。与实际答案相差
1
0
−
5
10^{-5}
10−5 以内的答案可以被接受。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[3.00000,14.50000,11.00000]
解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入:root = [3,9,20,15,7]
输出:[3.00000,14.50000,11.00000]
提示:
- 树中节点数量在 [ 1 , 1 0 4 ] [1, 10^4] [1,104] 范围内
- − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^{31} <= Node.val <= 2^{31} - 1 −231<=Node.val<=231−1
思路:BFS
使用 BFS 进行层次遍历。
不需要使用两个队列来分别存储当前层的节点和下一层的节点
- 因为在开始遍历一层的节点时,当前队列中的节点数就是当前层的节点数,只要控制遍历这么多节点数,就能保证这次遍历的都是当前层的节点。
代码:(Java、C++)
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> ans = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while(!que.isEmpty()){
int len = que.size();
double sum = 0;
for(int i = 0; i < len; i++){
root = que.poll();
sum += root.val;
if(root.left != null) que.add(root.left);
if(root.right != null) que.add(root.right);
}
ans.add(sum / len);
}
return ans;
}
}
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int len = que.size();
double sum = 0;
for(int i = 0; i < len; i++){
root = que.front();
que.pop();//pop返回的是void
sum += root->val;
if(root->left != NULL) que.push(root->left);
if(root->right != NULL) que.push(root->right);
}
ans.push_back(sum / len);
}
return ans;
}
};
运行结果:
复杂度分析:
-
时间复杂度: O ( n ) O(n) O(n),其中
n
是二叉树中的节点个数。 广度优先搜索需要对每个节点访问一次,时间复杂度是 O ( n ) O(n) O(n)。 需要对二叉树的每一层计算平均值,时间复杂度是 O ( h ) O(h) O(h),其中h
是二叉树的高度,任何情况下都满足 h ≤ n h≤n h≤n。 因此总时间复杂度是 O ( n ) O(n) O(n)。 -
空间复杂度: O ( n ) O(n) O(n),其中
n
是二叉树中的节点个数。空间复杂度取决于队列开销,队列中的节点个数不会超过n
。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章
- ☆打卡算法☆LeetCode 224. 基本计算器 算法解析
- 老梁你居然说刷LeetCode Easy找不到工作,你一定没做过Java
- leetcode-84柱状图中最大的矩形(单调栈)「建议收藏」
- Leetcode题目048-旋转图像
- LeetCode(Weekly Contest 187)题解
- LeetCode 237. 删除链表中的节点
- LeetCode 66. 加一
- leetcode 20. 有效的括号 js实现
- LeetCode 1236/1242 设计一个(多线程)爬虫解法
- golang刷leetcode:设计LFU缓存结构
- JavaScript刷LeetCode拿offer之失败-滑动窗口
- 前端工程师leetcode算法面试必备-二叉树深度广度遍历1
- 每日一道leetcode:11. 盛最多水的容器
- LeetCode每日一题:实现strStr()
- leetcode: 二叉树的层序遍历
- LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先