当前位置: 首页 > news >正文

二叉树的锯齿形遍历,力扣

目录

题目:

我们直接看题解吧:

快速理解解题思路小建议:

解题方法:

相似题目对比分析:

解题分析:

解题思路:

补充说明:

思路优化:

代码实现(层序遍历+倒序):


题目地址:

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;}
}

相关文章:

二叉树的锯齿形遍历,力扣

目录 题目&#xff1a; 我们直接看题解吧&#xff1a; 快速理解解题思路小建议&#xff1a; 解题方法&#xff1a; 相似题目对比分析&#xff1a; 解题分析&#xff1a; 解题思路&#xff1a; 补充说明&#xff1a; 思路优化&#xff1a; 代码实现(层序遍历倒序)&#xff1a; 题…...

避免Arrays.asList陷阱:优雅处理结构性修改的方法

临近年终&#xff0c;项目交付排期比较紧张&#xff0c;导致很多时候&#xff0c;Code Review 往往是走马观花&#xff0c;没有严格执行。最近&#xff0c;一个实习生就产生了一个十分低级的代码BUG。笔者感觉这个问题&#xff0c;对于实习生&#xff0c;尤其是刚入职的 应届 J…...

微信小程序(三十六)事件传参

注释很详细&#xff0c;直接上代码 上一篇 新增内容&#xff1a; 1.传参步骤 2.传参接收解构步骤 源码&#xff1a; index.wxml <button type"primary" bind:tap"onclick" mark:index"{{0}}" mark:remb"{{1}}" class"But&quo…...

编译原理与技术(三)——语法分析(二)自顶向下-递归下降

一、语法分析的两种方法 自顶向下&#xff08;Top-down&#xff09;&#xff1a; 针对输入串&#xff0c;从文法的开始符号出发&#xff0c;尝试根据产生式规则推导&#xff08;derive&#xff09;出该输入串。 从根部开始构造语法树。 自底向上&#xff08;Bottom-up&#…...

okhttp 的 拦截器

拦截器有很多作用&#xff0c;实现就是责任链模式&#xff0c;细节&#xff0c;等我有时间补上。 后面有时间更新一下。 OkHttp最核心的工作是在 getResponseWithInterceptorChain() 中进行&#xff0c;在进入这个方法分析之前&#xff0c;我们先来了 解什么是责任链模式&…...

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学设计模式之原型模式

如果对象的创建成本比较大&#xff0c;而同一个类的不同对象之间差别不大&#xff08;大部分字段都相同&#xff09;&#xff0c;在这种情况下&#xff0c;我们可以利用对已有对象&#xff08;原型&#xff09;进行复制&#xff08;或者叫拷贝&#xff09;的方式来创建新对象&a…...

博客|基于Springboot的个人博客系统设计与实现(源码+数据库+文档)

个人博客系统目录 目录 基于Springboot的个人博客系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员功能实现 &#xff08;1&#xff09;用户管理 &#xff08;2&#xff09;文章分类管理 &#xff08;3&#xff09;公告信息管理 &#xff08;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上传文件不允许重名

需求&#xff1a; 用户可以多文件上传 &#xff0c;在上传到服务器之前需要检查服务器中有无重名的文件&#xff0c;如果有会返回重名文件的名称数组&#xff0c;这些文件需要一个一个的向用户确认是否要覆盖重传。确认完毕后再上传到服务器。 检查文件重名&#xff1a; //上传…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Video媒体组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Video媒体组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Video媒体组件 用于播放视频文件并控制其播放状态的组件。 子组件 无 接口…...

Linux操作系统运维-Docker的基础知识梳理总结

Linux操作系统运维-Docker的基础知识梳理总结 docker用来解决不同开发人员软件调试时环境不统一的问题&#xff0c;保证了程序调试时运行环境的一致性。docker的设计理念便是一处镜像&#xff0c;处处运行&#xff0c;即通过产生用户软件&#xff0c;运行环境及其运行配置的统一…...

PMP考试成绩如何查询?

PMP考试成绩已经陆续出来了&#xff0c;出成绩时间大概一周左右&#xff0c;没收到的别着急&#xff0c;先把如何查询成绩路径弄清楚。 【如何查询成绩】 1、输入网址&#xff08;PMI官网&#xff0c;不知道网址的私戳&#xff09;&#xff0c;点击 Log In 如果忘记 PMI 的账…...

【Scala】 2. 函数

2. 函数 scala运算符、if … else …两部分和C语言类型&#xff0c;这里不再赘述&#xff0c;这里从for循环开始讲讲scala和c/c的不同之处。 2.1 for循环 scala中主要包含to和until两个关键字&#xff0c;下面分别看看两者的用法&#xff0c;看例子就行了。 (1) to的用法 …...

14.0 Zookeeper环球锁实现原理

全局锁是控制全局系统之间同步访问共享资源的一种方式。 下面介绍zookeeper如何实现全民锁&#xff0c;讲解他锁和共享锁两类全民锁。 排他锁 排他锁&#xff08;Exclusive Locks&#xff09;&#xff0c;又被称为写锁或独占锁&#xff0c;如果事务T1对数据对象O1加上排他锁…...

课时16:本地变量_普通变量

2.2.2 普通变量 学习目标 这一节&#xff0c;我们从 基础知识、简单实践、小结 三个方面来学习。 基础知识 变量分类 所谓的本地变量就是&#xff1a;在当前系统的某个环境下才能生效的变量&#xff0c;作用范围小。本地变量按照变量值的生成方式包含两种&#xff1a;普通…...

阿里云服务器centos_7_9_x64位,3台,搭建k8s集群

目录 1.环境信息 2.搭建过程 2.1 安装Docker源 2.2 安装Docker 2.3 安装kubeadm&#xff0c;kubelet和kubectl 2.4 部署Kubernetes Master(node1) 2.5 安装Pod网络插件&#xff08;CNI&#xff09; 2.6 加入Kubernetes Node 2.7 测试kubernetes集群 3.部署 Dashboard…...

代码随想录第二十八天

第七章 回溯算法part04 ​ ● 93.复原IP地址 ​ ● 78.子集 ​ ● 90.子集II 详细布置 93.复原IP地址 本期本来是很有难度的&#xff0c;不过 大家做完 分割回文串 之后&#xff0c;本题就容易很多了 题目链接/文章讲解&#xff1a;https://programmercarl.com/0093.%E5…...

【python】绘制爱心图案

以下是一个简单的Python代码示例&#xff0c;它使用turtle模块绘制一个代表爱和情人节的心形图案。 首先&#xff0c;请确保计算机上安装了Python和turtle模块。然后&#xff0c;将以下代码保存到一个.py文件中&#xff0c;运行它就可以看到爱心图案的绘制过程。 import turt…...

在 Elastic Agent 中为 Logstash 输出配置 SSL/TLS

要将数据从 Elastic Agent 安全地发送到 Logstash&#xff0c;你需要配置传输层安全性 (TLS)。 使用 TLS 可确保你的 Elastic Agent 将加密数据发送到受信任的 Logstash 服务器&#xff0c;并且你的 Logstash 服务器从受信任的 Elastic Agent 客户端接收数据。 先决条件 确保你…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...