LeetCode 0103.二叉树的锯齿形层序遍历:层序遍历 + 适时翻转

【LetMeFly】103.二叉树的锯齿形层序遍历:层序遍历 + 适时翻转

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

给你二叉树的根节点 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

方法一:层序遍历 + 适时翻转

前言

相信大家已经做过关于层序遍历的练习了,没有做过的建议先做一做,可以参考这篇题解:LeetCode 102.二叉树的层序遍历 + 针对C++的使用空间优化 (可能不同于常规做法)

思路

这道题与之不同的是,每隔一层需要变化一下遍历方向。

真的要变换遍历方向吗?其实不然:

我们只需要在正常遍历的基础上使用一个变量来记录当前这一层是否需要翻转,若需翻转则在这一层遍历结束后reverse一下最后一层即可。

  • 时间复杂度 O ( N ) O(N) O(N),其中 N N N是节点个数
  • 空间复杂度 O ( N 2 ) O(N2) O(N2),其中 N 2 N2 N2是节点最多的一层的节点数

AC代码

C++
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ans;bool ifReverse = false;queue<TreeNode*> q;if (root) {q.push(root);}while (q.size()) {ans.push_back({});for (int _ = q.size(); _ > 0; _--) {TreeNode* thisNode = q.front();q.pop();ans.back().push_back(thisNode->val);if (thisNode->left) {q.push(thisNode->left);}if (thisNode->right) {q.push(thisNode->right);}}if (ifReverse) {reverse(ans.back().begin(), ans.back().end());}ifReverse = !ifReverse;}return ans;}
};
Python
# from typing import List, Optional# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:ans = []ifReverse = Falseq = []if root:q.append(root)while q:ans.append([])for _ in range(len(q)):thisNode = q[0]q = q[1:]ans[-1].append(thisNode.val)if thisNode.left:q.append(thisNode.left)if thisNode.right:q.append(thisNode.right)if ifReverse:ans[-1].reverse()ifReverse = not ifReversereturn ans

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136126902

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

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

相关文章

Stable Diffusion WebUI 界面介绍

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 大家好&#xff0c;我是水滴~~ 本文主要对 Stable Diffusion WebUI 的界面进行简单的介绍&#xff0c;让你对该 WebUI 有个大致的了解&#xff0c;为后面的深入学习打下一个基础。主要内容包…

Vscode vim 插件使用Ctrl+C和V进行复制粘贴到剪切板

Vscode vim 插件使用CtrlC和V进行复制粘贴到剪切板 使用这一个插件的时候复制粘贴和其他软件互动的时候体验不好, 并且不可以用Ctrl c, Ctrl v很不爽 "vim.commandLineModeKeyBindings": [{"before" : ["Ctrl", "c"],"after&q…

LabVIEW高速信号测量与存储

LabVIEW高速信号测量与存储 介绍了LabVIEW开发的高速信号测量与存储系统&#xff0c;解决实验研究中信号捕获的速度和准确性问题。通过高效的数据处理和存储解决方案&#xff0c;本系统为用户提供了一种快速、可靠的信号测量方法。 项目背景 在科学研究和工业应用中&#xf…

爱上JVM——常见问题(一):JVM组成

1 JVM组成 1.1 JVM由那些部分组成&#xff0c;运行流程是什么&#xff1f; 难易程度&#xff1a;☆☆☆ 出现频率&#xff1a;☆☆☆☆ JVM是什么 Java Virtual Machine Java程序的运行环境&#xff08;java二进制字节码的运行环境&#xff09; 好处&#xff1a; 一次编写&…

【4.1计算机网络】TCP-IP协议簇

目录 1.OSI七层模型2.常见协议及默认端口3.TCP与UDP的区别 1.OSI七层模型 osi七层模型&#xff1a; 1.应用层 2.表示层 3.会话层 4.传输层&#xff1a;TCP为可靠的传输层协议。 5.网络层 6.数据链路层 7.物理层 2.常见协议及默认端口 3.TCP与UDP的区别 例题1. 解析&#xff1…

XR行业首家|李未可科技通过深度合成服务算法备案

2月18日&#xff0c;国家网信办发布第四批深度合成服务算法备案。 根据《互联网信息服务深度合成管理规定》第十九条规定&#xff0c;具有舆论属性或者社会动员能力的深度合成服务提供者&#xff0c;应当按照《互联网信息服务算法推荐管理规定》履行备案和变更、注销备案手续。…

2.19作业

1.使用fread,fwrite完成两个文件之间的拷贝 程序代码&#xff1a; #include <myhead.h>int main(int argc, const char *argv[]) {if(argc!3){printf("input file error\n");printf("usage:./a.out srcfile destfile\n");return -1;}FILE *fpNULL;…

【JavaEE】_HTTP响应

目录 1. 首行 2. 报头header 3.空行 4. 正文body 1. 首行 响应首行&#xff1a;版本号状态码状态码描述&#xff1b; HTTP状态码描述了这次响应的结果&#xff08;比如成功、失败&#xff0c;以及失败原因等&#xff09;&#xff1b; 1. HTTP状态码有&#xff1a; &#…

华为配置旁挂二层组网隧道转发示例

配置旁挂二层组网隧道转发示例 组网图形 业务需求组网需求数据规划配置思路配置注意事项操作步骤配置文件扩展阅读 业务需求 企业用户通过WLAN接入网络&#xff0c;以满足移动办公的最基本需求。且在覆盖区域内移动发生漫游时&#xff0c;不影响用户的业务使用。 组网需求 AC组…

嵌入式学习-C++-Day6

思维导图 作业 以下是一个简单的比喻&#xff0c;将多态概念与生活中的实际情况相联系&#xff1a; 比喻&#xff1a;动物园的讲解员和动物表演 想象一下你去了一家动物园&#xff0c;看到了许多不同种类的动物&#xff0c;如狮子、大象、猴子等。现在&#xff0c;动物园里有一…

树状数组算法模版

树状数组算法模版 树状数组算法原理基本操作模版题 树状数组算法原理 这里注意&#xff1a;C[x]的含义和lowbit()函数 基本操作 最基本的操作主要是两种 1.改变某个数&#xff08;单点修改&#xff09; 2.区间查询 模版题 #include<iostream> #include<cstdio>usin…

NS安装-CentOS服务器安装Nightscout CGM

NS CGM 安装必要条件 有自己的云服务器好像没有2&#xff0c;有云服务器就行了 安装顺序 先安装数据库&#xff0c;目前支持的是 MongoDB &#xff0c;官方推荐4&#xff0c;其实目前最新版本就行。可以用宝塔安装&#xff0c;比较简单克隆代码&#xff0c;我是放到 /opt/ns…

Django实战:部署项目 【资产管理系统】,Django完整项目学习研究(项目全解析,部署教程,非常详细)

导言 关于Django&#xff0c;我已经和大家分享了一些知识&#xff0c;考虑到一些伙伴需要在实际的项目中去理解。所以我上传了一套Django的项目学习源码&#xff0c;已经和本文章进行了绑定。大家可以自行下载学习&#xff0c;考虑到一些伙伴是初学者&#xff0c;几年前&#…

HCIA-HarmonyOS设备开发认证V2.0-IOT硬件子系统-SPI

目录 一、 SPI 概述二、SPI 模块相关API三、接口调用实例四、SPI HDF驱动开发4.1、开发步骤(待续...) 坚持就有收获 一、 SPI 概述 SPI 是串行外设接口&#xff08;Serial Peripheral Interface&#xff09;是一种高速的全双工同步的通信总线。 SPI 是由 Motorola 公司开发&a…

【天衍系列 01】深入理解Flink的 FileSource 组件:实现大规模数据文件处理

文章目录 01 基本概念02 工作原理03 数据流实现04 项目实战4.1 项目结构4.2 maven依赖4.3 StreamFormat读取文件数据4.4 BulkFormat读取文件数据4.5 使用小结 05 数据源比较06 总结 01 基本概念 Apache Flink 是一个流式处理框架&#xff0c;被广泛应用于大数据领域的实时数据…

虚拟机+麒麟海光+达梦数据库linux 安装教程

一 下载 虚拟机下载地址下载 VMware Workstation Pro | CN 达梦数据库下载地址 产品下载 | 达梦数据库 (dameng.com) 银河麒麟下载地址 国产操作系统、银河麒麟、中标麒麟、开放麒麟、星光麒麟——麒麟软件官方网站 (kylinos.cn) 二 安装 虚拟机安装 https://www.cnblogs…

嵌入式学习C++ Day7

嵌入式学习C Day7 一、思维导图 二、作业

设计模式之委派模式

文章目录 前言正文一、生活中的例子二、Java代码实现2.1 类设计2.2 代码实现2.2.1 Employee2.2.2 ArchitectureDesignEmployer2.2.3 BackEmployer2.2.4 FrontEmployer2.2.5 Leader2.2.6 EmployeeStrongPointEnum2.2.7 Boss 2.3 测试2.3.1 Client2.3.2 测试结果 三、委派模式的优…

Docker Desktop 链接windos 安装的redis和mysql

1.1.先在容器安装项目 2.链接redis和mysql配置 redis和mysql是在windos安装的&#xff0c;使用的是小p管理器安装的 项目链接 DB_DRIVERmysql DB_HOSThost.docker.internal DB_PORT3306 DB_DATABASEyunxc_test DB_USERNAMEyunxc_test DB_PASSWORDtest123456... DB_CHARSETutf…

【医学大模型】Text2MDT :从医学指南中,构建医学决策树

Text2MDT &#xff1a;从医学指南中&#xff0c;构建医学决策树 提出背景Text2MDT 逻辑Text2MDT 实现框架管道化框架端到端框架 效果 提出背景 论文&#xff1a;https://arxiv.org/pdf/2401.02034.pdf 代码&#xff1a;https://github.com/michael-wzhu/text2dt 假设我们有一…