当前位置:网站首页>leetcode刷题:二叉树04(二叉树的层序遍历)
leetcode刷题:二叉树04(二叉树的层序遍历)
2022-07-04 03:51:00 【涛涛英语学不进去】
102.二叉树的层序遍历
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
乍一看挺复杂,仔细做一下,一招秒。
package com.programmercarl.tree;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/** * @ClassName LevelOrder * @Descriotion TODO * @Author nitaotao * @Date 2022/7/3 11:55 * @Version 1.0 * https://leetcode.cn/problems/binary-tree-level-order-traversal/ * 102. 二叉树的层序遍历 **/
public class LevelOrder {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Deque<TreeNode> deque = new ArrayDeque();
if (root == null) {
return result;
}
//入队
deque.offer(root);
while (!deque.isEmpty()) {
int size=deque.size();
List<Integer> floor = new ArrayList();
while (size > 0) {
//每次遍历一层
TreeNode node = deque.poll();
floor.add(node.val);
if (node.left != null) {
deque.offer(node.left);
}
if (node.right != null) {
deque.offer(node.right);
}
size--;
}
result.add(floor);
}
return result;
}
}
层序遍历,大 list
包小 list 。 每个小 list 为一层。
一层一层来,记录当前队列的长度,就是上一层有多少元素,这次就弹出多少次,把新元素继续加在队列尾部即可。
看了一下题解,我的属于广度优先遍历,还有深度优先遍历。
/** * 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<List<Integer>> resList = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
checkFun01(root, 0);
return resList;
}
public void checkFun01(TreeNode node, Integer deep) {
if (node == null) {
return;
}
deep++;
if (resList.size() < deep) {
//当层级增加时,list的Item也增加,利用List的索引值进行层级结点
List<Integer> item = new ArrayList<>();
resList.add(item);
}
resList.get(deep - 1).add(node.val);
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
}
有一说一我看到不太懂,有点像先准备一个 List ,然后深度优先遍历,把结果按层序遍历的索引放上去。
边栏推荐
- Go 语言入门很简单:Go 实现凯撒密码
- 三年进账35.31亿,这个江西老表要IPO了
- Three years of graduation, half a year of distance | community essay solicitation
- The three-year revenue is 3.531 billion, and this Jiangxi old watch is going to IPO
- laravel admin里百度编辑器自定义路径和文件名
- 疫情来袭--远程办公之思考|社区征文
- I was tortured by my colleague's null pointer for a long time, and finally learned how to deal with null pointer
- JDBC 进阶
- Database SQL statement summary, continuous update
- Two sides of the evening: tell me about the bloom filter and cuckoo filter? Application scenario? I'm confused..
猜你喜欢
Two commonly used graphics can easily realize data display
还原窗口位置的微妙之处
[untitled]
拼夕夕二面:说说布隆过滤器与布谷鸟过滤器?应用场景?我懵了。。
Confession code collection, who says program apes don't understand romance
CesiumJS 2022^ 源码解读[0] - 文章目录与源码工程结构
【CSRF-01】跨站请求伪造漏洞基础原理及攻防
Msgraphmailbag - search only driveitems of file types
MySQL maxscale realizes read-write separation
02 specific implementation of LS command
随机推荐
[book club issue 13] multimedia processing tool ffmpeg tool set
“软硬皆施”,助力建成新型云计算数据中心
I was tortured by my colleague's null pointer for a long time, and finally learned how to deal with null pointer
Flink学习6:编程模型
Programmers' telecommuting is mixed | community essay solicitation
Pointer array and array pointer
The three-year revenue is 3.531 billion, and this Jiangxi old watch is going to IPO
*. No main manifest attribute in jar
Deep thinking on investment
Pytest multi process / multi thread execution test case
JS实现文字滚动 跑马灯效果
还原窗口位置的微妙之处
Lnk2038 detected a mismatch of "runtimelibrary": the value "md_dynamicrelease" does not match the value "mdd_dynamicdebug" (in main.obj)
毕业三年,远程半年 | 社区征文
02 ls 命令的具体实现
疫情来袭--远程办公之思考|社区征文
hbuildx中夜神模拟器的配置以及热更新
Mindmanager2022 efficient and easy to use office mind map MindManager
Why is the probability of pod increasing after IPtable
Smart subway | cloud computing injects wisdom into urban subway transportation