⭐北邮复试刷题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 …...
机械臂robotic-arm--8.snapshot.7
机械臂作为自动化领域的核心设备,其设计精度与功能稳定性直接影响任务执行效率。以robotic-arm--8.snapshot.7为例,其核心作用体现在多维度空间定位与复杂轨迹规划能力上。通过集成高精度伺服电机与闭环控制系统,该型号机械臂可实现亚毫米级重…...
Stable Diffusion XL 1.0开源大模型教程:灵感画廊app.py核心逻辑解读
Stable Diffusion XL 1.0开源大模型教程:灵感画廊app.py核心逻辑解读 “见微知著,凝光成影。将梦境的碎片,凝结为永恒的视觉诗篇。” 如果你对AI绘画感兴趣,一定听说过Stable Diffusion XL 1.0这个强大的开源模型。但面对复杂的参…...
Joy-Con Toolkit:让Switch玩家掌控设备的开源管理方案
Joy-Con Toolkit:让Switch玩家掌控设备的开源管理方案 【免费下载链接】jc_toolkit Joy-Con Toolkit 项目地址: https://gitcode.com/gh_mirrors/jc/jc_toolkit 为什么Switch玩家需要专属管理工具? 当你插入Switch游戏卡带时,是否担心…...
从音乐均衡器到语音降噪:深入浅出玩转数字谐振器设计与MATLAB仿真
从音乐均衡器到语音降噪:深入浅出玩转数字谐振器设计与MATLAB仿真 你是否曾在调整音乐播放器的均衡器时好奇——那些滑动条如何精确控制特定频段的声音强弱?这背后隐藏的数字信号处理魔法,正是我们今天要探索的数字谐振器技术。无论是提取语音…...
给CUDA新手的3DGS代码导读:从forward.cu到backward.cu,一步步拆解渲染流程
给CUDA新手的3DGS代码导读:从forward.cu到backward.cu,一步步拆解渲染流程 第一次看到3D Gaussian Splatting(3DGS)的CUDA代码时,我盯着那些复杂的核函数和内存操作发了半小时呆。作为从PyTorch转型过来的研究者&#…...
NaViL-9B图文问答入门必看:纯文本+图像理解双模式快速上手
NaViL-9B图文问答入门必看:纯文本图像理解双模式快速上手 1. 认识NaViL-9B多模态模型 NaViL-9B是一款原生支持多模态交互的大语言模型,由专业研究团队开发。它最大的特点是能同时处理纯文本问答和图片内容理解任务,就像一个同时精通文字和视…...
模电小白必看:3种基本放大电路实战对比(附电路图+避坑指南)
模电入门实战:三大基础放大电路深度解析与避坑指南 刚接触模拟电路时,面对共射极、共集极和共基极这三种基本放大电路,很多初学者都会感到困惑——它们看起来相似,但特性却大不相同。本文将用面包板搭建的真实电路和示波器实测波形…...
如何选择最适合的开源付费墙绕过工具?5款热门方案深度测评
如何选择最适合的开源付费墙绕过工具?5款热门方案深度测评 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字内容付费阅读日益普及的今天,开源工具为用户提…...
SEO_详解SEO优化的完整工作流程与执行要点
<h2>SEO优化的重要性</h2> <p>在当前数字化时代,网站的可见度和流量直接关系到企业的市场竞争力。搜索引擎优化(SEO)作为提升网站在搜索引擎中排名的关键手段,其重要性不言而喻。SEO不仅能帮助企业吸引更多的自…...
Ubuntu 22.04 换源+Docker安装+镜像加速
Ubuntu 22.04 换源Docker安装镜像加速 前言 本文针对 Ubuntu 22.04 LTS 系统,先更换国内镜像源提升下载速度,再完成 Docker 引擎与 Compose 插件安装,最后配置 Docker 国内镜像加速,全程无报错、可直接复制执行,适配 V…...
