⭐北邮复试刷题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 …...
终极指南:Autoenv如何彻底解决团队开发环境配置难题
终极指南:Autoenv如何彻底解决团队开发环境配置难题 【免费下载链接】autoenv 项目地址: https://gitcode.com/gh_mirrors/aut/autoenv Autoenv是一款强大的目录环境管理工具,能够在您进入包含.env文件的目录时自动执行其中的环境配置࿰…...
TranslucentTB深度解析:如何用5MB内存实现Windows任务栏的视觉革命
TranslucentTB深度解析:如何用5MB内存实现Windows任务栏的视觉革命 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB 在Windows…...
跨平台嵌入式开发库gear-lib功能解析与应用
1. 跨平台嵌入式开发基础库gear-lib深度解析1.1 项目概述gear-lib是一组采用POSIX C标准实现的通用基础库集合,其设计目标是为嵌入式系统、物联网设备及网络服务开发提供跨平台支持。该库支持Linux、Windows、Android和iOS等多种操作系统环境,采用MIT开源…...
OpenClaw镜像体验报告:GLM-4.7-Flash云端部署3大优势
OpenClaw镜像体验报告:GLM-4.7-Flash云端部署3大优势 1. 为什么选择云端体验OpenClaw 上周我在本地笔记本上折腾OpenClaw时,经历了所有开发者都熟悉的"依赖地狱"——Node.js版本冲突、Python环境污染、系统权限问题接踵而至。当终于看到open…...
3步解锁苹果电脑新玩法:用PlayCover畅玩iOS游戏和应用
3步解锁苹果电脑新玩法:用PlayCover畅玩iOS游戏和应用 【免费下载链接】PlayCover Community fork of PlayCover 项目地址: https://gitcode.com/gh_mirrors/pl/PlayCover 还在羡慕朋友在iPad上玩热门手游,而你的Mac只能干看着?想知道…...
从音乐均衡器到语音降噪:深入浅出玩转数字谐振器设计与MATLAB仿真
从音乐均衡器到语音降噪:深入浅出玩转数字谐振器设计与MATLAB仿真 你是否曾在调整音乐播放器的均衡器时好奇——那些滑动条如何精确控制特定频段的声音强弱?这背后隐藏的数字信号处理魔法,正是我们今天要探索的数字谐振器技术。无论是提取语音…...
告别移植头疼!用STM32CubeMX快速复用正点原子LCD库的3个关键步骤
告别移植头疼!用STM32CubeMX快速复用正点原子LCD库的3个关键步骤 在嵌入式开发中,复用成熟的驱动代码是提升效率的关键。正点原子的LCD库因其稳定性和易用性广受欢迎,但在STM32CubeMX生成的HAL工程中直接使用却常常遇到各种兼容性问题。本文将…...
Go代码越容易被AI写,Go工程师越值钱
Go代码越容易被AI写,Go工程师越值钱。 这句话听起来矛盾,但它是这个系列的终极结论。 前提是——你的价值不在"写代码"。 这是「AI工程时代三部曲」的收官篇。第一篇我们聊了Agent框架设计为什么比模型选型更重要,第二篇聊了技术债…...
DeepSeek-OCR 2技术突破:动态视觉token重排效果展示
DeepSeek-OCR 2技术突破:动态视觉token重排效果展示 1. 引言 想象一下,当你阅读一份复杂的学术论文时,眼睛不会机械地从左上角扫到右下角,而是会自然地跳过标题、关注图表、追踪公式推导,甚至在不同的文本栏之间灵活…...
密码学实战:从古典密码到AES,手把手教你用Python实现加密算法
密码学实战:从古典密码到AES的Python实现之旅 密码学作为信息安全的核心支柱,其发展历程就像一部浓缩的科技史。从凯撒大帝用过的简单字母替换,到如今保护我们银行卡交易的AES算法,加密技术始终在与破解者进行着无声的较量。本文…...
