Leetcode 二叉树的锯齿形层序遍历

在这里插入图片描述

算法思想:

这段代码实现了 二叉树的锯齿形层序遍历,其核心思想是基于广度优先搜索(BFS)进行层序遍历,并根据当前层数决定从左到右或从右到左的顺序来组织每一层的节点值。

level.addlevel.addFirst 有点类似单链表的头插法和尾插法

详细步骤:
  1. 树节点定义
    定义了一个 TreeNode 类来表示二叉树的节点,每个节点包含:

    • val:节点的值
    • left:左子节点
    • right:右子节点
  2. 主算法逻辑

    • 定义了一个 zigzagLevelOrder 方法,用来执行锯齿形层序遍历。
    • 输入:二叉树的根节点 root
    • 输出:一个嵌套的列表 List<List<Integer>>,表示每一层的节点值,按照锯齿形排列。
  3. 初始化

    • 如果 root 为空,直接返回空列表。
    • 创建一个 Queue(队列)用来辅助进行层序遍历,并将根节点入队。
    • 定义一个布尔变量 leftToRight,初始为 true,用来表示当前层是否按从左到右的顺序进行。
  4. 按层遍历(循环处理每一层)

    • 在队列不为空的情况下,每次处理一整层的节点:
      • 获取当前层的节点数 size(队列长度)。
      • 创建一个 LinkedList 来存储当前层的节点值。
      • 遍历当前层的所有节点:
        • 从队列中取出节点。
        • 如果是从左到右(leftToRighttrue),直接将节点值追加到列表末尾。
        • 如果是从右到左,将节点值插入到列表头部(通过 addFirst 方法实现)。
        • 将当前节点的左右子节点(如果存在)加入队列,供下一层遍历使用。
    • 将当前层的列表加入最终结果 result
    • 翻转布尔变量 leftToRight,切换到下一层的遍历顺序。
  5. 返回结果

    • 最后返回 result,包含每一层的节点值。
核心优化点:
  • 锯齿形插入
    • 通过 LinkedListaddaddFirst 方法灵活控制节点值的插入顺序,而无需额外对结果进行反转操作。
  • 层序遍历的 BFS 实现
    • 利用队列实现按层处理,每一层结束后通过 leftToRight 切换方向,确保按照锯齿形顺序遍历。

算法复杂度分析:

  1. 时间复杂度

    • 每个节点被访问一次,且每次访问操作的插入复杂度为 (O(1)) 或 (O(1))(在 LinkedList 的头部或尾部操作)。
    • 总时间复杂度为 (O(N)),其中 (N) 是二叉树的节点数。
  2. 空间复杂度

    • 主要由队列的存储和结果列表 result 决定。
    • 在最坏情况下(例如完全二叉树的最后一层),队列可能需要存储 (O(N)) 个节点。
    • 空间复杂度为 (O(N))。

示例运行过程(输入示例中的树):

输入树结构:

    3/ \9  20/  \15   7
第1层:
  • queue 初始包含根节点 [3]
  • leftToRight = true,从左到右读取当前层:
    • 输出 [3]
  • 下一层加入节点 [9, 20]
  • 切换方向:leftToRight = false
第2层:
  • queue 包含 [9, 20]
  • leftToRight = false,从右到左读取当前层:
    • 输出 [20, 9]
  • 下一层加入节点 [15, 7]
  • 切换方向:leftToRight = true
第3层:
  • queue 包含 [15, 7]
  • leftToRight = true,从左到右读取当前层:
    • 输出 [15, 7]

最终结果为 [[3], [20, 9], [15, 7]]


如果有其他问题或需要进一步优化解释,请随时告诉我!

java 实现

class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if(root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean lefttoright = true;while(!queue.isEmpty()) {int levelsize = queue.size();// level 用于存放每层的遍历结果LinkedList<Integer> level = new LinkedList<>();for(int i = 0; i < levelsize; i++) {TreeNode node = queue.poll();if(lefttoright) {level.add(node.val);} else {level.addFirst(node.val);}if(node.left != null) {queue.offer(node.left);}if(node.right != null) {queue.offer(node.right);}}lefttoright = !lefttoright;result.add(level);}return result;}
}

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

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

相关文章

OpenCV 图像轮廓查找与绘制全攻略:从函数使用到实战应用详解

摘要&#xff1a;本文详细介绍了 OpenCV 中用于查找图像轮廓的 cv2.findContours() 函数以及绘制轮廓的 cv2.drawContours() 函数的使用方法。涵盖 cv2.findContours() 各参数&#xff08;如 mode 不同取值对应不同轮廓检索模式&#xff09;及返回值的详细解析&#xff0c;搭配…

Linux操作系统2-进程控制3(进程替换,exec相关函数和系统调用)

上篇文章&#xff1a;Linux操作系统2-进程控制2(进程等待&#xff0c;waitpid系统调用&#xff0c;阻塞与非阻塞等待)-CSDN博客 本篇代码Gitee仓库&#xff1a;Linux操作系统-进程的程序替换学习 d0f7bb4 橘子真甜/linux学习 - Gitee.com 本篇重点&#xff1a;进程替换 目录 …

0基础学前端系列 -- 深入理解 HTML 布局

在现代网页设计中&#xff0c;布局是至关重要的一环。良好的布局不仅能提升用户体验&#xff0c;还能使内容更具可读性和美观性。HTML&#xff08;超文本标记语言&#xff09;结合 CSS&#xff08;层叠样式表&#xff09;为我们提供了多种布局方式。本文将详细介绍流式布局、Fl…

Springboot集成通义大模型

1.先到阿里云平台开头阿里云白炼账号&#xff0c;创建apiKey 2. 引入maven依赖 <dependency><groupId>com.alibaba</groupId><artifactId>dashscope-sdk-java</artifactId><version>2.8.3</version></dependency><!-- htt…

哈希表算法题

目录 题目一——1. 两数之和 - 力扣&#xff08;LeetCode&#xff09; 1.1.暴力解法1 1.2.暴力解法2 1.2.哈希表解法 题目二——面试题 01.02. 判定是否互为字符重排 - 力扣&#xff08;LeetCode&#xff09; 2.1.哈希表解法 2.2.排序解法 题目三——217. 存在重复元…

Cookie跨域

跨域&#xff1a;跨域名&#xff08;IP&#xff09; 跨域的目的是共享Cookie。 session操作http协议&#xff0c;每次既要request&#xff0c;也要response&#xff0c;cookie在创建的时候会产生一个字符串然后随着response返回。 全网站的各个页面都会带着登陆的时候的cookie …

个人博客接入github issue风格的评论,utteranc,gitment

在做个人博客的时候&#xff0c;如果你需要评论功能&#xff0c;但是又不想构建用户体系和评论模块&#xff0c;那么可以直接使用github的issue提供的接口&#xff0c;对应的开源项目有utteranc和gitment&#xff0c;尤其是前者。 它们的原理是一样的&#xff1a;在博客文章下…

React第十节组件之间传值之context

1、Context 使用creatContext() 和 useContext() Hook 实现多层级传值 概述&#xff1a; 在我们想要每个层级都需要某一属性&#xff0c;或者祖孙之间需要传值时&#xff0c;我们可以使用 props 一层一层的向下传递&#xff0c;或者我们使用更便捷的方案&#xff0c;用 creatC…

JVM_垃圾收集器详解

1、 前言 JVM就是Java虚拟机&#xff0c;说白了就是为了屏蔽底层操作系统的不一致而设计出来的一个虚拟机&#xff0c;让用户更加专注上层&#xff0c;而不用在乎下层的一个产品。这就是JVM的跨平台&#xff0c;一次编译&#xff0c;到处运行。 而JVM中的核心功能其实就是自动…

RPA:电商订单处理自动化

哈喽&#xff0c;大家好&#xff0c;我是若木&#xff0c;最近闲暇时间较多&#xff0c;于是便跟着教程做了一个及RPA&#xff0c;谈到这个&#xff0c;可能很多人并不是很了解&#xff0c;但是实际上&#xff0c;这玩意却遍布文末生活的边边角角。话不多说&#xff0c;我直接上…

字符型注入‘)闭合

前言 进行sql注入的时候&#xff0c;不要忘记闭合&#xff0c;先闭合再去获取数据 步骤 判断是字符型注入 用order by获取不了显位&#xff0c;select也一样 是因为它是’)闭合&#xff0c;闭合之后&#xff0c;就可以获取数据了 最后就是一样的步骤

springboot车辆管理系统设计与实现(代码+数据库+LW)

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了车辆管理系统的开发全过程。通过分析车辆管理系统管理的不足&#xff0c;创建了一个计算机管理车辆管理系统的方案。文章介绍了车辆管理系统的系统分析部分&…

C#.Net筑基 - 常见类型

01、结构体类型Struct 结构体 struct 是一种用户自定义的值类型&#xff0c;常用于定义一些简单&#xff08;轻量&#xff09;的数据结构。对于一些局部使用的数据结构&#xff0c;优先使用结构体&#xff0c;效率要高很多。 可以有构造函数&#xff0c;也可以没有。因此初始化…

Unity项目性能优化列表

1、对象池 2、检查内存是否泄露。内存持续上升(闭包、委托造成泄露) 3、检查DrawCall数量&#xff0c;尽量减少SetPassCall 4、尽量多的利用四种合批 动态合批(Dynamic Batching)静态合批(Static Batching)GPUInstancingSRP Batcher 动态合批消耗内存把多个网格组合在一起合并…

ComfyUI | ComfyUI桌面版发布,支持winmac多平台体验,汉化共享等技巧!(内附安装包)

ComfyUI 桌面版正式推出&#xff0c;支持 Windows 与 macOS 等多平台&#xff0c;为 AI 绘画爱好者带来全新体验。其安装包便捷易用&#xff0c;开启了轻松上手之旅。汉化共享功能更是一大亮点&#xff0c;打破语言障碍&#xff0c;促进知识交流与传播。在操作上&#xff0c;它…

贪心-区间问题——acwing

题目一&#xff1a;最大不相交区间数量 908. 最大不相交区间数量 - AcWing题库 分析 跟区间选点一样。区间选点&#xff1a;贪心——acwing-CSDN博客 代码 #include<bits/stdc.h> using namespace std;const int N 1e510;struct Range {int l, r;// 重载函数bool op…

【C语言】字符串左旋的三种解题方法详细分析

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C语言 文章目录 &#x1f4af;前言&#x1f4af;题目描述&#x1f4af;方法一&#xff1a;逐字符移动法&#x1f4af;方法二&#xff1a;使用辅助空间法&#x1f4af;方法三&#xff1a;三次反转法&#x1f4af;方法对…

肿瘤微环境中单细胞的泛癌分类

scRNA-seq可以揭示肿瘤微环境 (TME) 内细胞异质性的宝贵见解&#xff0c;scATOMIC是一种用于恶性和非恶性细胞的注释工具。在 300,000 个癌症、免疫和基质细胞上训练了 scATOMIC&#xff0c;为 19 种常见癌症定义了一个泛癌症参考&#xff0c;scATOMIC优于当前的分类方法。在 2…

《算法导论》英文版前言To the teacher第3段研习录:题海战术有没有?

【英文版】 We have included 957 exercises and 158 problems. Each section ends with exercises, and each chapter ends with problems. The exercises are generally short questions that test basic mastery of the material. Some are simple self-check thought exer…

docker使用(镜像、容器)

docker基础使用 文章目录 前言1.镜像操作1.1命令介绍1.2.案例实操1.2.1查找镜像1.2.2下载镜像1.2.3查看当前镜像 2.容器操作2.1命令2.1.1容器创建与启动2.1.2. 容器查看2.1.3. 容器操作2.1.4. 容器删除2.1.5. 容器日志2.1.6. 容器内文件操作2.1.7. 容器内命令执行2.1.8. 其他常…