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

⭐北邮复试刷题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 &#xff0c;返回其节点值的 锯齿形层序遍历 。&#xff08;即先从左往右&#xff0c;再从右往左进行下一层遍历&#xff0c;以此类推&#xff0c;层与层之间交替进行&#xff09;。 示例 1&#xff1a;输入&#xff1a…...

文件上传漏洞--Upload-labs--Pass07--点绕过

一、什么是点绕过 在Windows系统中&#xff0c;Windows特性会将文件后缀名后多余的点自动删除&#xff0c;在网页源码中&#xff0c;通常使用 deldot()函数 对点进行去除&#xff0c;若发现网页源代码中没有 deldot() 函数&#xff0c;则可能存在 点绕过漏洞。通过点绕过漏洞&…...

MySQL高级特性篇(1)-JSON数据类型的应用

MySQL是一种常用的关系型数据库管理系统&#xff0c;它提供了多种数据类型&#xff0c;其中包括JSON数据类型。JSON&#xff08;JavaScript Object Notation&#xff09;是一种常用的数据交换格式&#xff0c;它以键值对的形式组织数据&#xff0c;并支持嵌套和数组结构。MySQL…...

如何用Qt实现一个无标题栏、半透明、置顶(悬浮)的窗口

在Qt框架中&#xff0c;要实现一个无标题栏、半透明、置顶&#xff08;悬浮&#xff09;的窗口&#xff0c;需要一些特定的设置和技巧。废话不多说&#xff0c;下面我将以DrawClient软件为例&#xff0c;介绍一下实现这种效果的四个要点。 要点一&#xff1a;移除标题栏&#…...

ViT: transformer在图像领域的应用

文章目录 1. 概要2. 方法3. 实验3.1 Compare with SOTA3.2 PRE-TRAINING DATA REQUIREMENTS3.3 SCALING STUDY3.4 自监督学习 4. 总结参考 论文&#xff1a; An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale 代码&#xff1a;https://github.com…...

Sora 的工作原理(及其意义)

原文&#xff1a;How Sora Works (And What It Means) 作者&#xff1a; DAN SHIPPER OpenAI 的新型文本到视频模型为电影制作开启了新篇章 DALL-E 提供的插图。 让我们先明确一点&#xff0c;我们不会急急忙忙慌乱。我们不会预测乌托邦或预言灾难。我们要保持冷静并... 你…...

Java学习笔记2024/2/16

知识点 面向对象 题目1&#xff08;完成&#xff09; 定义手机类&#xff0c;手机有品牌(brand),价格(price)和颜色(color)三个属性&#xff0c;有打电话call()和sendMessage()两个功能。 请定义出手机类&#xff0c;类中要有空参、有参构造方法&#xff0c;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 中&#xff0c;苹果为我们带来了全新的可观察框架 Observation&#xff0c;它是观察者开发模式在 Swift 中的一个全新实现。 除了自身本领过硬以外&#xff0c;Observation 框架和 SwiftUI 搭配起来也能相得益彰&#xff0c;事倍功半。不过 Observable 对象…...

分享一个学英语的网站

名字叫&#xff1a;公益大米网​​​​​​​ Freerice 这个网站是以做题的形式来记忆单词&#xff0c;题干是一个单词&#xff0c;给出4个选项&#xff0c;需要选出其中最接近题干单词的选项。 答对可以获得10粒大米&#xff0c;网站的创办者负责捐赠。如图 触发某些条件&a…...

【动态规划】【C++算法】2742. 给墙壁刷油漆

作者推荐 【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 本文涉及知识点 动态规划汇总 LeetCode2742. 给墙壁刷油漆 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time &#xff0c;分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有…...

【后端高频面试题--设计模式上篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 往期精彩内容 【后端高频面试题–设计模式上篇】 【后端高频面试题–设计模式下篇】 【后端高频…...

P3141 [USACO16FEB] Fenced In P题解

题目 如果此题数据要小一点&#xff0c;那么我们可以用克鲁斯卡尔算法通过&#xff0c;但是这个数据太大了&#xff0c;空间会爆炸&#xff0c;时间也会爆炸。 我们发现&#xff0c;如果用 MST 做&#xff0c;那么很多边的边权都一样&#xff0c;我们可以整行整列地删除。 我…...

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的安装有两种方式&#xff1a; 1、yum安装&#xff1a;安装快速&#xff0c;但是无法在安装的时候带上想要的第三方包 2、…...

Qt之条件变量QWaitCondition详解(从使用到原理分析全)

QWaitCondition内部实现结构图&#xff1a; 相关系列文章 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、机器批量执行、机器批量上传、在线查看日志、定时调度任务、应…...

【后端高频面试题--设计模式下篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 后端高频面试题--设计模式下篇 往期精彩内容设计模式总览模板方法模式怎么理解模板方法模式模板方…...

这才是大学生该做的副业,别再痴迷于游戏了!

感谢大家一直以来的支持和关注&#xff0c;尤其是在我的上一个公众号被关闭后&#xff0c;仍然选择跟随我的老粉丝们&#xff0c;你们的支持是我继续前行的动力。为了回馈大家长期以来的陪伴&#xff0c;我决定分享一些实用的干货&#xff0c;这些都是我亲身实践并且取得成功的…...

Ubuntu20.04 安装jekyll

首先使根据官方文档安装&#xff1a;Jekyll on Ubuntu | Jekyll • Simple, blog-aware, static sites 如果没有报错&#xff0c;就不用再继续看下去了。 我这边在执行gem install jekyll bundler时报错&#xff0c;所以安装了rvm&#xff0c;安装rvm可以参考这篇文章Ubuntu …...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...