二叉树的层次遍历 · Binary Tree Level Order Traversal
2024-08-24 07:12:49
[抄题]:
给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)
[思维问题]:
[一句话思路]:
用queue存每一层
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 每一层level存的东西都是不一样的,所以要在queue非空的循环中再新建。不要当成全局变量。
- root为空时,返回result空数组,而不是null四个字母
- stack用pop 弹出来,queue用poll 拉出来,想想也比较形象。root非空用null,数据结构非空要用isEmpty()函数
[二刷]:
- 不要忘了写特判
[三刷]:
[四刷]:
[五刷]:
[总结]:
把size单独设成变量 ,每次都取一遍 多取几次总不会错 (否则取左、右会导致queue.size()很大,level会多加)
树的BFS不会重复,所以不需要用哈希表。只要用queue即可。
[复杂度]:Time complexity: O(n) Space complexity: O(n)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
- 用queue存每一层,实现先进先出
- 注意格式:接口 名 = new 具体实现;eg 队列可以用静态数组、链表linked list来实现
- List<List<Integer>> result = new ArrayList<List<Integer>>(); list里面装list,效果是一层一层的:
[
[3],
[9,20],
[15,7]
]
[其他解法]:
2queue,dummy node
[Follow Up]:
- 把结果反过来写:用Collections.reverse(result);函数
- DFS:迭代式的深度优先搜索,不断放宽MAX_LEVEL条件,直到某层没有点。(历史上,内存有限的时候用)
[LC给出的题目变变变]:
637. Average of Levels in Binary Tree
103. Binary Tree Zigzag Level Order Traversal
public class Solution {
/*
* @param root: A Tree
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>(); if (root == null) {
return result;
} queue.offer(root);
while (!queue.isEmpty()) {//
int size = queue.size();
List<Integer> level = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode curt = queue.poll();//
level.add(curt.val);
if (curt.left != null) {
queue.offer(curt.left);
}
if (curt.right != null) {
queue.offer(curt.right);
}
}
result.add(level);
}
return result;
}
}
最新文章
- Struts2实现ajax的两种方式
- chart.js插件生成折线图时数据普遍较大时Y轴数据不从0开始的解决办法[bubuko.com]
- oracle在impdp时报ORA-31655和ORA-39154
- Java多线程系列--“基础篇”02之 常用的实现多线程的两种方式
- 安装 Dubbo 管理控制台
- php修改和增加xml结点属性
- HDFS常用命令
- 服务器部署_centos 安装jdk手记
- jQuery ajax传递特殊字符串问题
- 哥德尔,图灵和康托尔 part 1 哥德尔编号
- 利用python进行数据分析之绘图和可视化
- 解决xshell连接不上Ubuntu
- .NET 动态脚本语言
- SpringBoot ( 七 ) :springboot + mybatis 多数据源最简解决方案
- 2017年末大总结(by一个软件开发实习生)
- Linux 中使用 firewalld
- jquery的cookie插件
- debian 安装libreoffice6.1 转换pdf
- anaconda 出现add 。。。进不去
- iOS WKWebView (NSURLProtocol)拦截js、css,图片资源
热门文章
- 1082 Read Number in Chinese (25 分)
- Linux系统文件名字体不同的颜色都代表什么
- TensorFlow函数:tf.FIFOQueue队列
- javascript的面向对象思想知识要点
- Windows Event 事件
- python3中reduce()函数的使用方法示例
- 「CQOI2016」K 远点对
- MySql 链接字符串
- 隐藏bat脚本运行时弹出的黑窗口,以隐藏进程在后台执行.
- 0_Simple__simpleTexture + 0_Simple__simpleTextureDrv