当前位置:网站首页>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 ,然后深度优先遍历,把结果按层序遍历的索引放上去。
边栏推荐
- Smart subway | cloud computing injects wisdom into urban subway transportation
- Calculate the odd sum of 1~n (1~100 as an example)
- Katalon框架测试web(二十六)自动发邮件
- 【华为云IoT】读书笔记之《万物互联:物联网核心技术与安全》第3章(上)
- Brief explanation of depth first search (with basic questions)
- Exercices de renforcement des déclarations SQL (MySQL 8.0 par exemple)
- Flink学习7:应用程序结构
- Flink学习8:数据的一致性
- Es network layer
- I was tortured by my colleague's null pointer for a long time, and finally learned how to deal with null pointer
猜你喜欢
[Logitech] m720
[csrf-01] basic principle and attack and defense of Cross Site Request Forgery vulnerability
10 reasons for not choosing to use free virtual hosts
Penetration practice - sqlserver empowerment
Pytest multi process / multi thread execution test case
The maximum expiration time of client secret in azure ad application registration is modified to 2 years
MySQL maxscale realizes read-write separation
分布式系统:what、why、how
Sales management system of lightweight enterprises based on PHP
LNK2038 检测到“RuntimeLibrary”的不匹配项: 值“MD_DynamicRelease”不匹配值“MDd_DynamicDebug”(main.obj 中)
随机推荐
数据库SQL语句汇总,持续更新......
Simple dialogue system -- text classification using transformer
1289_FreeRTOS中vTaskSuspend()接口实现分析
Go 语言入门很简单:Go 实现凯撒密码
2022-07-03: there are 0 and 1 in the array. Be sure to flip an interval. Flip: 0 becomes 1, 1 becomes 0. What is the maximum number of 1 after turning? From little red book. 3.13 written examination.
SDP中的SPA
Idea configuration 360zip open by default -- external tools
Restore the subtlety of window position
Lnk2038 detected a mismatch of "runtimelibrary": the value "md_dynamicrelease" does not match the value "mdd_dynamicdebug" (in main.obj)
【读书会第十三期】视频文件的封装格式
指针数组和数组指针
Why is the probability of pod increasing after IPtable
Penetration practice - sqlserver empowerment
Cesiumjs 2022^ source code interpretation [0] - article directory and source code engineering structure
三菱M70宏变量读取三菱M80公共变量采集三菱CNC变量读取采集三菱CNC远程刀补三菱机床在线刀补三菱数控在线测量
支持首次触发的 Go Ticker
10 reasons for not choosing to use free virtual hosts
Exercices de renforcement des déclarations SQL (MySQL 8.0 par exemple)
Illustrated network: what is the hot backup router protocol HSRP?
Mindmanager2022 efficient and easy to use office mind map MindManager