【数据结构与算法 | 基础篇 | 队列篇】力扣102, 107

2024-05-29 21:52

本文主要是介绍【数据结构与算法 | 基础篇 | 队列篇】力扣102, 107,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 力扣102 : 二叉树的层序遍历

(1). 题

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

示例 1:

 

fbf1c4f33ddc948c764e9c9237acd91c.jpeg

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

(2). 思路

由题,可知方法返回一个集合,该集合的元素仍然是一个集合. 该题需要用到队列数据结构.如果二叉树是空树,直接返回空集合. 如果不是,则将根节点入队.由于根节点在队列中,将size初始化为1,n的作用则是用于更新size.while循环,只要队列不为空,那么就new一个集合,for循环依次出队,并将出队的节点的值add到集合中收集起来,如果其有左孩子或右孩子,则将该孩子节点入队,并将n++. 一次循环结束时,将小集合add入大集合中.

(3). 解

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> bl = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();if(root == null) {return bl;}deque.offer(root);int size = 1;int n = 0;//只要队列不为空while(!deque.isEmpty()) {List<Integer> l = new ArrayList<>();for(int i =0 ; i < size; i++) {TreeNode tn = deque.poll();l.add(tn.val);if(tn.left != null) {deque.offer(tn.left);n++;}if(tn.right != null) {deque.offer(tn.right);n++;}}size = n;n = 0;bl.add(l);}return bl;}
}

2. 力扣107 : 二叉树的层序遍历2

(1). 题

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

 

示例 1:

 

d247066a47d3d1cfeceba712880b907d.jpeg

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

(2). 思路

该题与力扣102题同源,只不过最后处理的时候多了一个出栈入栈的操作而已. 所以完全可以将102题的代码复制粘贴过来,然后添加一个栈结构,while循环中,不是直接将小集合添加到大集合中,而是做一个压栈的操作.while循环结束以后,将栈中元素全部弹出,add入大集合,将其返回即可.

(3). 解

/*** 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>> levelOrderBottom(TreeNode root) {List<List<Integer>> bl = new ArrayList<>();Deque<TreeNode> deque = new LinkedList<>();Deque<List<Integer>> stack = new LinkedList<>();if(root == null) {return bl;}deque.offer(root);int size = 1;int n = 0;//只要队列不为空while(!deque.isEmpty()) {List<Integer> l = new ArrayList<>();for(int i =0 ; i < size; i++) {TreeNode tn = deque.poll();l.add(tn.val);if(tn.left != null) {deque.offer(tn.left);n++;}if(tn.right != null) {deque.offer(tn.right);n++;}}size = n;n = 0;stack.push(l);}while(!stack.isEmpty()) {bl.add(stack.pop());}return bl;}
}

这篇关于【数据结构与算法 | 基础篇 | 队列篇】力扣102, 107的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1014735

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘