637. Average of Levels in Binary Tree 二叉树的层次遍历再求均值
2024-10-05 19:05:25
[抄题]:
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].
[暴力解法]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
BFS写不熟
[一句话思路]:
(3先生)先加头、先判Empty、先取长度
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 没概念:BFS中的for循环是针对当前这一层的操作,add的元素都属于下一层
- 二叉树层遍历,q中存的是节点,记住就行了
[二刷]:
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
BFS里既然取了长度,就用在for循环中
[复杂度]:Time complexity: O(n) Space complexity: O(n)
所有点放进去一次,拿出来一次,最终还是n
[英文数据结构或算法,为什么不用别的数据结构或算法]:
[关键模板化代码]:
q.offer(root);
//isEmpty()
while (! q.isEmpty()) {
//get length
int n = q.size();
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
//corner case
List<Double> ans = new ArrayList<Double>();
Queue<TreeNode> q = new LinkedList<TreeNode>(); if (root == null) {
return ans;
}
//bfs
//offer root
q.offer(root);
//isEmpty()
while (! q.isEmpty()) {
//get length
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);
}
}
ans.add(sum / n);
}
//return
return ans;
}
}
最新文章
- android studio上的基本动画实现(第一篇)
- 烂泥:阿里云RDS本地恢复数据
- linux工具apt、yum和dnf运用
- iOS开发:自定义控件实现手势解锁
- Java多线程6:synchronized锁定类方法、volatile关键字及其他
- 框架SpringMVC笔记系列 一 基础
- mysql 误删除ibdata1之后如何恢复
- ARC工程中添加非ARC文件
- centos 下安装ati显卡驱动方法
- SICP-2.2-数据的抽象
- 用runtime封装归档(encoding)
- (predicted == labels).sum().item()作用
- 2018-2019-1 20189206 《Linux内核原理与分析》第九周作业
- P2163 [SHOI2007]园丁的烦恼(cdq分治)
- jquery 学习(一):jQuery 简介
- response设置编码格式
- Swift:宏定义
- 02-老马jQuery教程-jQuery事件处理
- 我的Quartz笔记
- 分割流 SequenceInputStream (转)