二叉树的锯齿形遍历,力扣
目录
题目:
我们直接看题解吧:
快速理解解题思路小建议:
解题方法:
相似题目对比分析:
解题分析:
解题思路:
补充说明:
思路优化:
代码实现(层序遍历+倒序):
题目地址:
103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)
难度:中等
今天刷二叉树的锯齿形遍历,大家有兴趣可以点上面链接,看看题目要求,试着做一下。
题目:
二叉树的锯齿形遍历,给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

我们直接看题解吧:
快速理解解题思路小建议:
可以先简单看一下解题思路,然后照着代码看思路,会更容易理解一些。
审题目+事例+提示:
注意输出结果为二维列表
解题方法:
方法1:层序遍历+双端队列(广度优先搜索)
方法2:层序遍历+倒序
相似题目对比分析:
相似题目解题链接:-> 二叉树的层序遍历,力扣-CSDN博客
此题是「102 二叉树的层序遍历」的变种,最后输出的要求有所变化,要求我们按层数的奇偶来决定每一层的输出顺序,即结果打印顺序需要交替变化。
解题分析:
规定二叉树的根节点为第 0 层,
如果当前层数是偶数,从左至右输出当前层的节点值,
否则,从右至左输出当前层的节点值。
因此,可以沿用第 102 题的思想,修改广度优先搜索,对树进行逐层遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度 size,每次从队列中取出 size 个元素进行拓展,然后进行下一次迭代。
为了满足题目要求的返回值为「先从左往右,再从右往左」交替输出的锯齿形,我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。双端队列是一个可以在队列任意一端插入元素的队列。
解题思路:
利用双端队列的两端可添加元素的特性,设打印列表(双端对列)tmp,规定:
奇数层则添加值tmp尾部,
偶数层则添加值tmp头部。
另外:
方法1解题,代码简短、容易实现,但需要判断每个节点的所在层奇偶性,即冗余了 N次判断。
具体流程:
1、创建队列queue与列表res
2、BFS循环(当deque为空时跳出循环):
a.创建新列表tmp(用于临时存储当前层的遍历结果)
b.当前层的遍历循环(循环次数为当前层的节点数(即deque长度)):
·出队:队首元素出队赋值节点node
·打印:若为奇数层,将node.val添加至tmp尾部,反之
·添加子节点:若node的左()右节点非空,则加入deque
c.将当前层结果tmp转为list并加入res.
3、返回打印结果列表res.
可结合理解->103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode)
代码实现:
/*** 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>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();//创建双端队列,存放每层树的节点List<List<Integer>> res = new ArrayList<>();//创建二维列表,存储遍历所得节点值if (root != null) queue.add(root); //若根节点非空,则将根节点添加至queue队列while (!queue.isEmpty()) {//BFS循环,当deque为空时跳出循环LinkedList<Integer> tmp = new LinkedList<>();//创建新列表tmp(用于临时存储当前层的遍历结果)for(int i = queue.size(); i > 0; i--) {//循环次数为当前层的节点数(即deque长度)TreeNode node = queue.poll();//队首元素出队赋值节点nodeif (res.size() % 2 == 0) tmp.addLast(node.val);//若为奇数层,将node.val添加至tmp尾部,反之else tmp.addFirst(node.val);if (node.left != null) queue.add(node.left);//若node的左节点非空,则加入dequeif (node.right != null) queue.add(node.right);//若node的右节点非空,则加入deque}res.add(tmp);//将当前层遍历结果添加到res}return res;}
}
补充说明:
1、特殊处理:当树的根节点为空,则直接返回空列表[]
2、 打印结果空列表 res ,包含根节点的双端队列 deque,相当于初始化操作 。
3、本题解题代码将链表 LinkedList 作为双端队列使用
4、注意:这个是伪锯齿形遍历,相当于只是结果字符串反转了而已,遍历都是从左往右遍历,只不过在组装结果的时候改变了顺序,而没有按照先从左往右,再从右往左进行下一层遍历。
思路优化:
由方法1解题可知该方法需要判断每个节点的所在层奇偶性,即冗余了 N次判断,
因此通过将奇偶层逻辑拆分,可以消除冗余的判断,进一步优化解题方法。
主要优化在 BFS 循环部分。
算法流程:
BFS 循环: 循环打印奇 / 偶数层,当 deque 为空时跳出。
打印奇数层: 从左向右打印,先左后右 加入下层节点。
若 deque 为空,说明向下无偶数层,则跳出。
打印偶数层: 从右向左 打印,先右后左 加入下层节点。
while (!deque.isEmpty()) {// 打印奇数层List<Integer> tmp = new ArrayList<>();for(int i = deque.size(); i > 0; i--) {// 从左向右打印TreeNode node = deque.removeFirst();tmp.add(node.val);// 先左后右加入下层节点if (node.left != null) deque.addLast(node.left);if (node.right != null) deque.addLast(node.right);}res.add(tmp);if (deque.isEmpty()) break; // 若为空则提前跳出// 打印偶数层tmp = new ArrayList<>();for(int i = deque.size(); i > 0; i--) {// 从右向左打印TreeNode node = deque.removeLast();tmp.add(node.val);// 先右后左加入下层节点if (node.right != null) deque.addFirst(node.right);if (node.left != null) deque.addFirst(node.left);}res.add(tmp);}
代码实现(层序遍历+倒序):
- 此方法的优点是只用列表即可,无需其他数据结构。
- 偶数层倒序: 若
res的长度为 奇数 ,说明当前是偶数层,则对tmp执行 倒序 操作。
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if (root != null) queue.add(root);while (!queue.isEmpty()) {List<Integer> tmp = new ArrayList<>();for(int i = queue.size(); i > 0; i--) {TreeNode node = queue.poll();tmp.add(node.val);//直接添加节点if (node.left != null) queue.add(node.left);//添加子节点if (node.right != null) queue.add(node.right);}//偶数层倒序:若res的长度为奇数,说明当前是偶数层,则对tmp执行倒序操作。if (res.size() % 2 == 1) Collections.reverse(tmp);res.add(tmp);}return res;}
}
相关文章:
二叉树的锯齿形遍历,力扣
目录 题目: 我们直接看题解吧: 快速理解解题思路小建议: 解题方法: 相似题目对比分析: 解题分析: 解题思路: 补充说明: 思路优化: 代码实现(层序遍历倒序): 题…...
避免Arrays.asList陷阱:优雅处理结构性修改的方法
临近年终,项目交付排期比较紧张,导致很多时候,Code Review 往往是走马观花,没有严格执行。最近,一个实习生就产生了一个十分低级的代码BUG。笔者感觉这个问题,对于实习生,尤其是刚入职的 应届 J…...
微信小程序(三十六)事件传参
注释很详细,直接上代码 上一篇 新增内容: 1.传参步骤 2.传参接收解构步骤 源码: index.wxml <button type"primary" bind:tap"onclick" mark:index"{{0}}" mark:remb"{{1}}" class"But&quo…...
编译原理与技术(三)——语法分析(二)自顶向下-递归下降
一、语法分析的两种方法 自顶向下(Top-down): 针对输入串,从文法的开始符号出发,尝试根据产生式规则推导(derive)出该输入串。 从根部开始构造语法树。 自底向上(Bottom-up&#…...
okhttp 的 拦截器
拦截器有很多作用,实现就是责任链模式,细节,等我有时间补上。 后面有时间更新一下。 OkHttp最核心的工作是在 getResponseWithInterceptorChain() 中进行,在进入这个方法分析之前,我们先来了 解什么是责任链模式&…...
Android:多线程下载网络图片
3.12 网络图片操作 1、通过URL请求获取网络图片 示例: 创建t_picture.xml,页面layout布局文件,一个Button按钮和一个ImageView容器显示图片。 <?xml version="1.0" encoding="utf-8"?><LinearLayout xmlns:android="http://schemas.a…...
跟着GPT学设计模式之原型模式
如果对象的创建成本比较大,而同一个类的不同对象之间差别不大(大部分字段都相同),在这种情况下,我们可以利用对已有对象(原型)进行复制(或者叫拷贝)的方式来创建新对象&a…...
博客|基于Springboot的个人博客系统设计与实现(源码+数据库+文档)
个人博客系统目录 目录 基于Springboot的个人博客系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员功能实现 (1)用户管理 (2)文章分类管理 (3)公告信息管理 (4&#…...
【gcc】webrtc发送侧计算 丢包率
大神的分析 : 提到: 每当收到cc-feedback或者收到RR-report的时候就能统计出丢包率,在cc-controller中就会调用SendSideBandwidthEstimation::UpdatePacketsLost()去更新丢包率,同时进行码率预估 G:\CDN\rtcCli\m98\src\modules\congestion_controller\goog_cc\send_side_b…...
elementui上传文件不允许重名
需求: 用户可以多文件上传 ,在上传到服务器之前需要检查服务器中有无重名的文件,如果有会返回重名文件的名称数组,这些文件需要一个一个的向用户确认是否要覆盖重传。确认完毕后再上传到服务器。 检查文件重名: //上传…...
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Video媒体组件
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Video媒体组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Video媒体组件 用于播放视频文件并控制其播放状态的组件。 子组件 无 接口…...
Linux操作系统运维-Docker的基础知识梳理总结
Linux操作系统运维-Docker的基础知识梳理总结 docker用来解决不同开发人员软件调试时环境不统一的问题,保证了程序调试时运行环境的一致性。docker的设计理念便是一处镜像,处处运行,即通过产生用户软件,运行环境及其运行配置的统一…...
PMP考试成绩如何查询?
PMP考试成绩已经陆续出来了,出成绩时间大概一周左右,没收到的别着急,先把如何查询成绩路径弄清楚。 【如何查询成绩】 1、输入网址(PMI官网,不知道网址的私戳),点击 Log In 如果忘记 PMI 的账…...
【Scala】 2. 函数
2. 函数 scala运算符、if … else …两部分和C语言类型,这里不再赘述,这里从for循环开始讲讲scala和c/c的不同之处。 2.1 for循环 scala中主要包含to和until两个关键字,下面分别看看两者的用法,看例子就行了。 (1) to的用法 …...
14.0 Zookeeper环球锁实现原理
全局锁是控制全局系统之间同步访问共享资源的一种方式。 下面介绍zookeeper如何实现全民锁,讲解他锁和共享锁两类全民锁。 排他锁 排他锁(Exclusive Locks),又被称为写锁或独占锁,如果事务T1对数据对象O1加上排他锁…...
课时16:本地变量_普通变量
2.2.2 普通变量 学习目标 这一节,我们从 基础知识、简单实践、小结 三个方面来学习。 基础知识 变量分类 所谓的本地变量就是:在当前系统的某个环境下才能生效的变量,作用范围小。本地变量按照变量值的生成方式包含两种:普通…...
阿里云服务器centos_7_9_x64位,3台,搭建k8s集群
目录 1.环境信息 2.搭建过程 2.1 安装Docker源 2.2 安装Docker 2.3 安装kubeadm,kubelet和kubectl 2.4 部署Kubernetes Master(node1) 2.5 安装Pod网络插件(CNI) 2.6 加入Kubernetes Node 2.7 测试kubernetes集群 3.部署 Dashboard…...
代码随想录第二十八天
第七章 回溯算法part04 ● 93.复原IP地址 ● 78.子集 ● 90.子集II 详细布置 93.复原IP地址 本期本来是很有难度的,不过 大家做完 分割回文串 之后,本题就容易很多了 题目链接/文章讲解:https://programmercarl.com/0093.%E5…...
【python】绘制爱心图案
以下是一个简单的Python代码示例,它使用turtle模块绘制一个代表爱和情人节的心形图案。 首先,请确保计算机上安装了Python和turtle模块。然后,将以下代码保存到一个.py文件中,运行它就可以看到爱心图案的绘制过程。 import turt…...
在 Elastic Agent 中为 Logstash 输出配置 SSL/TLS
要将数据从 Elastic Agent 安全地发送到 Logstash,你需要配置传输层安全性 (TLS)。 使用 TLS 可确保你的 Elastic Agent 将加密数据发送到受信任的 Logstash 服务器,并且你的 Logstash 服务器从受信任的 Elastic Agent 客户端接收数据。 先决条件 确保你…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
