⭐北邮复试刷题103. 二叉树的锯齿形层序遍历 (力扣每日一题)
103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
示例 1:输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]示例 2:输入:root = [1]
输出:[[1]]示例 3:输入:root = []
输出:[]提示:树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

题解:
方法一:按层模拟BFS
/*** 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 void reverse(List<Integer> list){int size = list.size();int tmp[] = new int[size];for(int i=0;i<size;i++){tmp[i] = list.get(i);}int index = 0;for(int i=size-1;i>=0;i--){list.set(index,tmp[i]);index++;}}public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if(root == null){return res;}Queue<TreeNode> queue = new LinkedList<>();boolean flag = true; // true代表-> false代表<-List<Integer> first = new ArrayList<>();first.add(root.val);if(root.left != null)queue.offer(root.left);if(root.right != null)queue.offer(root.right);res.add(first);while(!queue.isEmpty()){List<Integer> tmp = new ArrayList<>();int count = queue.size();while(count > 0){TreeNode node = queue.poll();if(node.left != null)queue.offer(node.left);if(node.right != null)queue.offer(node.right);tmp.add(node.val);count--;}flag = !flag;if(!flag){//对此时取到的tmp顺序取反reverse(tmp);}res.add(tmp);}return res;}
}
方法二:双端队列+奇偶
/*** 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) {List<List<Integer>> res = new ArrayList<>();if(root == null){return res;}Queue<TreeNode> queue = new LinkedList<>();int len = 1;// 奇数代表-> 偶数代表<-List<Integer> first = new LinkedList<>();first.add(root.val);if(root.left != null)queue.offer(root.left);if(root.right != null)queue.offer(root.right);res.add(first);len++;while(!queue.isEmpty()){// 队列依旧是传统队列,但是每一个加入到res中的小list都是用双端形式,从而形式上实现双端队列List<Integer> tmp = new LinkedList<>();// 也是因为链表形式相较于数组形式更利于反转int count = queue.size();while(count > 0){TreeNode node = queue.poll();if(node.left != null)queue.add(node.left); if(node.right != null)queue.offer(node.right);if(len % 2 == 0){tmp.addFirst(node.val); }else{tmp.addLast(node.val);}count--;}res.add(tmp);len++;}return res;}
}

相关文章:
⭐北邮复试刷题103. 二叉树的锯齿形层序遍历 (力扣每日一题)
103. 二叉树的锯齿形层序遍历 给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 示例 1:输入:…...
文件上传漏洞--Upload-labs--Pass07--点绕过
一、什么是点绕过 在Windows系统中,Windows特性会将文件后缀名后多余的点自动删除,在网页源码中,通常使用 deldot()函数 对点进行去除,若发现网页源代码中没有 deldot() 函数,则可能存在 点绕过漏洞。通过点绕过漏洞&…...
MySQL高级特性篇(1)-JSON数据类型的应用
MySQL是一种常用的关系型数据库管理系统,它提供了多种数据类型,其中包括JSON数据类型。JSON(JavaScript Object Notation)是一种常用的数据交换格式,它以键值对的形式组织数据,并支持嵌套和数组结构。MySQL…...
如何用Qt实现一个无标题栏、半透明、置顶(悬浮)的窗口
在Qt框架中,要实现一个无标题栏、半透明、置顶(悬浮)的窗口,需要一些特定的设置和技巧。废话不多说,下面我将以DrawClient软件为例,介绍一下实现这种效果的四个要点。 要点一:移除标题栏&#…...
ViT: transformer在图像领域的应用
文章目录 1. 概要2. 方法3. 实验3.1 Compare with SOTA3.2 PRE-TRAINING DATA REQUIREMENTS3.3 SCALING STUDY3.4 自监督学习 4. 总结参考 论文: An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale 代码:https://github.com…...
Sora 的工作原理(及其意义)
原文:How Sora Works (And What It Means) 作者: DAN SHIPPER OpenAI 的新型文本到视频模型为电影制作开启了新篇章 DALL-E 提供的插图。 让我们先明确一点,我们不会急急忙忙慌乱。我们不会预测乌托邦或预言灾难。我们要保持冷静并... 你…...
Java学习笔记2024/2/16
知识点 面向对象 题目1(完成) 定义手机类,手机有品牌(brand),价格(price)和颜色(color)三个属性,有打电话call()和sendMessage()两个功能。 请定义出手机类,类中要有空参、有参构造方法,set/get方法。 …...
XLNet做文本分类
import torch from transformers import XLNetTokenizer, XLNetForSequenceClassification from torch.utils.data import DataLoader, TensorDataset # 示例文本数据 texts ["This is a positive example.", "This is a negative example.", "Anot…...
Swift 5.9 新 @Observable 对象在 SwiftUI 使用中的陷阱与解决
概览 在 Swift 5.9 中,苹果为我们带来了全新的可观察框架 Observation,它是观察者开发模式在 Swift 中的一个全新实现。 除了自身本领过硬以外,Observation 框架和 SwiftUI 搭配起来也能相得益彰,事倍功半。不过 Observable 对象…...
分享一个学英语的网站
名字叫:公益大米网 Freerice 这个网站是以做题的形式来记忆单词,题干是一个单词,给出4个选项,需要选出其中最接近题干单词的选项。 答对可以获得10粒大米,网站的创办者负责捐赠。如图 触发某些条件&a…...
【动态规划】【C++算法】2742. 给墙壁刷油漆
作者推荐 【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 本文涉及知识点 动态规划汇总 LeetCode2742. 给墙壁刷油漆 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ,分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有…...
【后端高频面试题--设计模式上篇】
🚀 作者 :“码上有前” 🚀 文章简介 :后端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 往期精彩内容 【后端高频面试题–设计模式上篇】 【后端高频面试题–设计模式下篇】 【后端高频…...
P3141 [USACO16FEB] Fenced In P题解
题目 如果此题数据要小一点,那么我们可以用克鲁斯卡尔算法通过,但是这个数据太大了,空间会爆炸,时间也会爆炸。 我们发现,如果用 MST 做,那么很多边的边权都一样,我们可以整行整列地删除。 我…...
Android Compose 一个音视频APP——Magic Music Player
Magic Music APP Magic Music APP Magic Music APP概述效果预览-视频资源功能预览Library歌曲播放效果预览歌曲播放依赖注入设置播放源播放进度上一首&下一首UI响应 歌词歌词解析解析成行逐行解析 视频播放AndroidView引入Exoplayer自定义Exoplayer样式横竖屏切换 歌曲多任…...
Nginx实战:安装搭建
目录 前言 一、yum安装 二、编译安装 1.下载安装包 2.解压 3.生成makefile文件 4.编译 5.安装执行 6.执行命令软连接 7.Nginx命令 前言 nginx的安装有两种方式: 1、yum安装:安装快速,但是无法在安装的时候带上想要的第三方包 2、…...
Qt之条件变量QWaitCondition详解(从使用到原理分析全)
QWaitCondition内部实现结构图: 相关系列文章 C之Pimpl惯用法 目录 1.简介 2.示例 2.1.全局配置 2.2.生产者Producer 2.3.消费者Consumer 2.4.测试例子 3.原理分析 3.1.源码介绍 3.2.辅助函数CreateEvent 3.3.辅助函数WaitForSingleObject 3.4.QWaitCo…...
OpenSource - 一站式自动化运维及自动化部署平台
文章目录 orion-ops 是什么重构特性快速开始技术栈功能预览添砖加瓦License orion-ops 是什么 orion-ops 一站式自动化运维及自动化部署平台, 使用多环境的概念, 提供了机器管理、机器监控报警、Web终端、WebSftp、机器批量执行、机器批量上传、在线查看日志、定时调度任务、应…...
【后端高频面试题--设计模式下篇】
🚀 作者 :“码上有前” 🚀 文章简介 :后端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 后端高频面试题--设计模式下篇 往期精彩内容设计模式总览模板方法模式怎么理解模板方法模式模板方…...
这才是大学生该做的副业,别再痴迷于游戏了!
感谢大家一直以来的支持和关注,尤其是在我的上一个公众号被关闭后,仍然选择跟随我的老粉丝们,你们的支持是我继续前行的动力。为了回馈大家长期以来的陪伴,我决定分享一些实用的干货,这些都是我亲身实践并且取得成功的…...
Ubuntu20.04 安装jekyll
首先使根据官方文档安装:Jekyll on Ubuntu | Jekyll • Simple, blog-aware, static sites 如果没有报错,就不用再继续看下去了。 我这边在执行gem install jekyll bundler时报错,所以安装了rvm,安装rvm可以参考这篇文章Ubuntu …...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
