【LeetCode】No.103. Binary Tree Zigzag Level Order Traversal -- Java Version

news/2024/3/28 21:10:03/文章来源:https://blog.csdn.net/qq_41071754/article/details/128102401

题目链接:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

1. 题目介绍(Binary Tree Zigzag Level Order Traversal)

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

【Translate】: 给定二叉树的根,返回其节点值的锯齿级顺序遍历。(例如,从左到右,然后下一个层将从右到左,并在两者之间交替)。

【测试用例】:

示例1:
testcase1

示例2:
tesecase2

【条件约束】:
Constraints

2. 题解

2.1 双堆栈

原题解来自于 tjcd 的 JAVA Double Stack Solution.

根据题意,要求Zigzag遍历,而不是像上一个 Binary Tree Level Order Traversal 依次按照顺序将遍历到的点数据存入列表中。而是要满足:①、奇数层的节点数据按照从左到右的顺序存入列表;②、偶数层的节点数据按照从右到左的顺序存入列表。这里就是通过双堆栈进行交替输出,一个堆栈存储奇数层,一个堆栈存储偶数层,关键就在于放入堆栈的顺序,奇序就从左到右放,偶序就从右向左放,最后输出即可。

/*** 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>> ans = new ArrayList<>();if(root == null) return ans;Stack<TreeNode> s1 = new Stack<>();Stack<TreeNode> s2 = new Stack<>();s1.push(root);TreeNode curr = new TreeNode();while(!s1.isEmpty() || !s2.isEmpty()){List<Integer> list = new ArrayList<>();while(!s1.isEmpty()){curr = s1.pop();list.add(curr.val);if(curr.left != null) s2.push(curr.left);if(curr.right != null) s2.push(curr.right);}ans.add(list);list = new ArrayList<>();while(!s2.isEmpty()){curr = s2.pop();list.add(curr.val);if(curr.right != null) s1.push(curr.right);if(curr.left != null) s1.push(curr.left);}if(!list.isEmpty()) ans.add(list);}return ans;}
}

act1

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_39048.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【学习笔记67】JavaScript中的闭包

一、认识函数的过程 1. 定义 在堆内存中开辟一段内存空间(XF001)把函数体的内容&#xff0c;完全百分百的照抄一份&#xff0c;存放在内存空间中(XF001)把内存空间的地址(XF001) 赋值给函数名2. 调用 根据函数名内存储的地址 (XF001) &#xff0c;去堆内存中找到对应函数会去…

R语言法国足球联赛球员多重对应分析(MCA)

数据集 fooball球员在场上的位置 数据来自国际足联的视频游戏FIFA 。游戏的特点是在游戏的各个方面评价每个球员的能力。等级是量化变量&#xff08;介于0和100之间&#xff09;&#xff0c;但我们将它们转换为分类变量。所有能力都被编码在4个等级&#xff1a;1.低/ 2.平均/ …

基于单片机技术的自动停车器的设计

目 录 摘 要 I Abstract II 1绪论 1 1.1课题研究背景 1 1.2国内外发展现状 1 1.3汽车自动停车器的研究目的 2 1.4课题研究的意义 2 2汽车停车器的功能设计 3 2.1汽车自动停车器的设计要求 3 2.2停车器的主要功能 3 3汽车自动停车器的硬件设计 5 3.1汽车自动停车器的硬件组成 5 …

数据存储——存储视频

数据存储——存储视频视频的数字化一、视频采样二、视频量化总结&#xff1a;视频数字化的过程视频的数字化 1.视频是图像&#xff08;帧&#xff09;在时间上的表示 图象是离散的视频&#xff0c;视频是连续的图像 2.视频储存 每一帧图像或帧被转化为位模式并加以储存 一、视…

三年城市NOH落地100城,毫末智行内部信剑指2025

11月29日&#xff0c;毫末智行董事长张凯、CEO顾维灏联合发布《毫末智行三周岁&#xff1a;三年磨一剑 利刃开新篇》的内部信&#xff0c;提到毫末愿景及战略目标&#xff1a;“让机器智能移动&#xff0c;给生活更多美好。”未来成长为一家产品矩阵覆盖全无人驾驶、机器人等多…

【Android App】Vulkan实现宇宙中旋转雷达动画效果(附源码和原始视频 超详细必看)

需要源码请点赞关注收藏后评论区留言私信~~~ 一、Vulkan简介 Vulkan是一个跨平台的图形绘制接口&#xff0c;被称为下一代OpenGL&#xff0c;因为尽管OpenGL提供了丰富的图形API&#xff0c;但他在底层实现的C代码早已封装起来&#xff0c;由于开发者修改不了底层代码&#xf…

​GENIUS: 根据草稿进行文本生成的预训练模型,可用于多种NLP任务的数据增强...

©PaperWeekly 原创 作者 | 郭必扬 单位 | 上海财经大学信息管理与工程学院AI Lab论文标题&#xff1a;GENIUS: Sketch-based Language Model Pre-training via Extreme and Selective Masking for Text Generation and Augmentation论文作者&#xff1a;Biyang Guo, Yeyu…

多线程,了解-概念-实现方式-常见方法-安全问题-死锁-生产者消费者

了解 简单了解多线程 是指从软件或者硬件上实现多个线程并发执行的技术。 具有多线程能力的计算机因有硬件支持而能够在同一时间执行多个线程&#xff0c;提升性能。 简单了解多线程 简单了解多线程 简单了解多线程 简单了解多线程 概念 线程相关的概念 并行&#xff1a;在同…

【车载开发系列】UDS诊断---电控单元复位 ($0x11)

【车载开发系列】UDS诊断—电控单元复位&#xff08;$0x11&#xff09; UDS诊断---电控单元复位&#xff08;$0x11&#xff09;【车载开发系列】UDS诊断---电控单元复位&#xff08;$0x11&#xff09;一.概念定义二.应用场景三.报文格式1&#xff09;请求2&#xff09;肯定响应…

Spark 3.0 - 8.ML Pipeline 之决策树原理与实战

目录 一.引言 二.决策树基础-信息熵 三.决策树的算法基础 - ID3 算法 四.ML 中决策树的构建 1.信息增益计算 2.连续属性划分 五.ML 决策树实战 1.Libsvm 数据与加载 2.StringIndexer 3.VectorIndexer 4.构建决策树与 Pipeline 5.测试与评估 6.获取决策树 六.总结…

基于PHP+MySQL企业网络推广平台系统的设计与实现

企业网络推广平台系统具有很强的信息指导性特征,采用PHP开发企业网络推广平台系统 给web带来了全新的动态效果,具有更加灵活和方便的交互性。在Internet中实现数据检索越来越容易,可以及时、全面地收集、存储大量的企业资源信息以及进行发布、浏览、搜索相关的信息。让企业、个…

C++ Reference: Standard C++ Library reference: Containers: list: list: cend

C官网参考链接&#xff1a;https://cplusplus.com/reference/list/list/cend/ 公有成员函数 <list> std::list::cend const_iterator cend() const noexcept; 返回结束的常量迭代器 返回一个指向容器结束后元素的const_iterator。 const_iterator是指向const内容的迭代…

Spring Boot FailureAnalyzer 应用场景

Spring Boot 自定义FailureAnalyzer 今天在学习Spring Boot 源码的过程中&#xff0c;在spring.factories 文件中无意中发现了FailureAnalyzer 这个接口。由于之前没有接触过&#xff0c;今天来学习一下 FailureAnalyzer 接口的作用。 在学习FailureAnalyzer之前, 我们先看以…

TMA三均线股票期货高频交易策略的R语言实现

趋势交易策略是至今应用最广泛以及最重要的投资策略之一&#xff0c;它的研究手段种类繁多&#xff0c;所运用的分析工具也纷繁复杂&#xff0c;其特长在于捕捉市场运动的大方向。股指期货市场瞬息万变&#xff0c;结合趋势分析方法&#xff0c;量化投资策略能够得到更有效的应…

Discourse 的左侧边栏可以修改吗

在默认的 Discourse 配置中&#xff0c;我们左侧的边栏可以根据自己的要求进行修改吗&#xff1f; 解决办法 针对自己登录的用户&#xff0c;你是可以自己调整左侧边栏的配置。 单击右上角你的个人头像&#xff0c;然后选择属性。 在切换的界面中&#xff0c;选择属性。 在出…

校园论坛(Java)——环境配置篇

校园论坛&#xff08;Java&#xff09;——环境配置篇 文章目录校园论坛&#xff08;Java&#xff09;——环境配置篇1、写在前面2、新建Maven项目2.1 引入相关依赖2.2 配置Tomcat环境3、项目发布测试4、项目代码5、参考资料1、写在前面 Windows版本&#xff1a;Windows10JDK版…

Python数据库编程之关系数据库API规范

Python关系数据库API规范 对于关系数据库的访问&#xff0c;Python社区已经制定出一个标准&#xff0c;称为Python Database API Specification。Mysql&#xff0c;Oracal等特定数据库模块遵从这一规范&#xff0c;而且可以添加更多特性。 高级数据库API定义了一组用于连接数…

YOLO V3 详解

YOLO V3 论文链接&#xff1a;YOLOv3: An Incremental Improvement 主要改进 Anchor: 9个大小的anchor&#xff0c;每个尺度分配3个anchor。Backbone改为Darknet-53, 引入了残差模块。引入了FPN&#xff0c;可以进行多个尺度的训练&#xff0c;同时对于小目标的检测有了一定…

R语言生存分析可视化分析

生存分析指的是一系列用来探究所感兴趣的事件的发生的时间的统计方法。 生存分析被用于各种领域&#xff0c;例如&#xff1a; 癌症研究为患者生存时间分析&#xff0c; “事件历史分析”的社会学 在工程的“故障时间分析”。 在癌症研究中&#xff0c;典型的研究问题如下…