力扣116. 填充每个节点的下一个右侧节点指针(详细讲解root根节点的理解)

题目:

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL

初始状态下,所有 next 指针都被设置为 NULL

示例 1:

输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。

示例 2:

输入:root = []
输出:[]

思路(详细分析根节点root):

这道题也套用了二叉树层序遍历的模板,不同的是该题有了next指针,把整个二叉树的同一层级的节点连接起来了

做这道题时我有些迷糊了,对于root到底是什么不太理解

之前 queue = collections.deque([root]) 里root是给定的树的结构里的根节点的值  如:[3,9,20,null,null,15,7] 表示的是二叉树的结构,其中 3 是根节点的值,而 [3,9,20,null,null,15,7] 是根节点及其左右子树的结构。因此,根节点是 3,而不是 [3,9,20,null,null,15,7]

但是在这道题目里(结合下面代码分析)

当我们在二叉树中使用 `next` 指针时,我们的目标是将同一层级的节点连接起来,形成一个横向的链表结构。因此,在这段代码中,返回的根节点 `root` 包含了整个树的结构,以及每个节点之间通过 `next` 指针连接形成的横向链表。这意味着,根节点 `root` 不仅包含了树的层次结构(每个节点的值、左右子节点),还包含了同一层节点之间的连接关系。

具体来说,在这段代码中,我们通过广度优先搜索(BFS)遍历树的节点,并使用队列 `queue` 来存储每一层的节点。在遍历过程中,对于每个节点,我们首先将其左右子节点加入队列中,然后在同一层的节点之间建立 `next` 指针的连接关系。例如,如果当前节点的左右子节点都存在,那么我们将左子节点的 `next` 指针指向右子节点;如果当前节点是同一层的最后一个节点(即 `i < size - 1`),那么将其 `next` 指针指向队列中的下一个节点。

因此,在这段代码中,返回的根节点 `root` 包含了整个树的结构,以及通过 `next` 指针连接形成的横向链表。这使得我们可以在树的层次结构基础上,通过 `next` 指针快速地访问同一层节点,实现了一种特殊的树的遍历方式。

代码:

 层序遍历(广度优先搜索)法

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':if not root:return rootfrom collections import dequequeue = deque([root])  # 创建一个双端队列,并将根节点放入队列中while queue:  # 当队列不为空时循环size = len(queue)  # 获取当前队列的长度for i in range(size):  # 遍历当前队列中的节点node = queue.popleft()  # 从队列中取出一个节点if node.left:  # 如果节点有左子节点,则将左子节点放入队列queue.append(node.left)if node.right:  # 如果节点有右子节点,则将右子节点放入队列queue.append(node.right)if i < size - 1:  # 如果不是当前层的最后一个节点,将当前节点的next指针指向队列中的下一个节点node.next = queue[0]return root  # 返回根节点

链表解法 :

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
class Solution:def connect(self, root: 'Node') -> 'Node':first = rootwhile first:cur = firstwhile cur:  # 遍历每一层的节点if cur.left: cur.left.next = cur.right  # 找左节点的nextif cur.right and cur.next: cur.right.next = cur.next.left  # 找右节点的nextcur = cur.next # cur同层移动到下一节点first = first.left  # 从本层扩展到下一层return root

复杂度分析:

层序遍历(广度优先搜索)法:
  • 时间复杂度:O(N),每个节点会被访问一次且只会被访问一次,即从队列中弹出,并建立 next 指针。
  • 空间复杂度:O(N),这是一棵完美二叉树,它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。
链表解法 :
  • 时间复杂度:O(N),每个节点只访问一次。

  • 空间复杂度:O(1),不需要存储额外的节点。

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

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

相关文章

LLM之RAG实战(一):使用Mistral-7b, LangChain, ChromaDB搭建自己的WEB聊天界面

一、RAG介绍 如何使用没有被LLM训练过的数据来提高LLM性能&#xff1f;检索增强生成&#xff08;RAG&#xff09;是未来的发展方向&#xff0c;下面将解释一下它的含义和实际工作原理。 ​ 假设您有自己的数据集&#xff0c;例如来自公司的文本文档。如何让ChatGPT和其他…

ZPLPrinter Emulator SDK for .NET 6.0.23.1123​ Crack

ZPLPrinter Emulator SDK for .NET 适用于 .NET 的 ZPLPrinter 仿真器 SDK 允许您通过编写 C# 或VB.NET 代码针对任何 .NET Framework、.NET CORE、旧版 ASP.NET MVC 和 CORE、Xamarin、Mono 和通用 Windows 平台 (UWP) 作业。 适用于 .NET 的 ZPLPrinter 仿真器 SDK 允许您将…

matplotlib与opencv图像读取与显示的问题

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 最近在用opencv和matplotlib展示图片,但是遇到了一些问题,这里展开说说 首先需要明确的是,opencv和matplotlib读取图片都是通道在最后,而前者默认可见光图像是BGR,后者是RGB.此外还有PIL以及imageio等读取图像的工具…

(学习笔记)Xposed模块编写(一)

前提&#xff1a;需要已经安装Xposed Installer 1. 新建一个AS项目 并把MainActvity和activity_main.xml这两个文件删掉&#xff0c;然后在AndriodManifest.xml中去掉这个Activity的声明 2. 在settings.gralde文件中加上阿里云的仓库地址&#xff0c;否则Xposed依赖无法下载 m…

9款热门API接口分享,值得收藏!

电商API接口 干货分享 开始 “ API是什么&#xff1f; API的主要目的是提供应用程序与开发人员以访问一组例程的能力&#xff0c;而又无需访问源码&#xff0c;或理解内部工作机制的细节。提供API所定义的功能的软件称作此API的实现。API是一种接口&#xff0c;故而是一种抽象…

Banana Pi最新的路由器板BPI-R4上市销售,基于MediaTek MT7988A

Banana Pi 发布了一款新的路由器板 Banana Pi BPI-R4&#xff0c;基于配备四核 Arm CPU 的 MediaTek MT7988A SoC。该板不仅仅是Raspberry Pi 的另一个替代品&#xff0c;而且是用于家庭网络和自动化的设备。 Banana Pi BPI-R4 的外形尺寸比单板计算机更像网络设备。对于那些希…

Python函数的基本使用(一)

Python函数的基本使用&#xff08;一&#xff09; 一、函数概述二、函数的定义2.1 函数的语法2.2 语法说明2.3 函数定义的方式2.4 总结 三、函数的调用3.1 函数调用语法3.2 语法说明3.3 函数调用 四、函数的参数4.1 参数的分类4.2 必需参数4.3 默认值参数4.4 关键字参数4.5 不定…

风变科技千万营收的AIGC项目,在Fanbook成功落地,专访风变科技CMO江育麟

在AIGC时代&#xff0c;创作生产力被下放到了每一位普通人身上&#xff0c;然后用户与AIGC应用之间还存在一定的认知与技术沟壑。 最近&#xff0c;【AIGC开放社区】注意到一款AIGC课程项目受到了相当的关注&#xff0c;让许多0基础的学员轻松地学会了使用AIGC技术的基本方法。…

风控交易系统跟单系统资管软件都有哪些功能特点?

资管分仓软件的主要功能就是母账户可以添加子账号&#xff0c;并且设置出入金&#xff0c;手续费、保证金、风控等功能&#xff0c;同时监控端更可以直观的看子账户的交易情况直接折线图展示更加直观&#xff0c;在监控端的最高权限可以直接一键平仓子账户&#xff08;如果子账…

基于jsp的搜索引擎

摘 要 随着互联网的不断发展和日益普及&#xff0c;网上的信息量在迅速地增长&#xff0c;在2004年4月&#xff0c;全球Web页面的数目已经超过40亿&#xff0c;中国的网页数估计也超过了3亿。 目前人们从网上获得信息的主要工具是浏览器&#xff0c;搜索引擎在网络中占有举足轻…

23种设计模式之C++实践(二)

23种设计模式之C++实践 3. 设计模式(二)组合型模式7. 适配器模式——不兼容结构的协调7.2:类适配器模式7.3:双向适配器模式适配器模式总结8.桥接模式——处理多维度变化桥接模式总结9. 组合模式——树形结构的处理9.2 透明组合模式9.3 安全组合模式组合模式总结10. 装饰模式…

【海思SS528 | VDEC】MPP媒体处理软件V5.0 | 视频解码模块——学习笔记

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

HR看好的字符函数和字符串处理函数!!!

本篇会加入个人的所谓‘鱼式疯言’❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言,而是理解过并总结出来通俗易懂的大白话,我会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的&#xff0c;可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 前言 在本篇…

智能监控平台/视频共享融合系统EasyCVR接入RTSP协议视频流无法播放原因是什么?

视频集中存储/云存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、智能分析等。AI智能/大数据视频分析EasyCVR平台已经广泛应用在工地、工厂、园区、楼…

深入理解Go语言GC机制

1、Go 1.3之前的标记-清除&#xff08;mark and sweep&#xff09;算法 Go 1.3之前的时候主要用的是普通的标记-清除算法&#xff0c;此算法主要由两个主要的步骤&#xff1a; 标记&#xff08;Mark phase&#xff09;清除&#xff08;Sweep phase&#xff09; 1&#xff09…

Spring Boot整合RabbitMQ

一、简介 在Spring项目中&#xff0c;可以使用Spring-Rabbit去操作RabbitMQ 尤其是在spring boot项目中只需要引入对应的amqp启动器依赖即可&#xff0c;方便的使用RabbitTemplate发送消息&#xff0c;使用注解接收消息。 一般在开发过程中&#xff1a; 生产者工程&#xf…

文心一言 VS 讯飞星火 VS chatgpt (148)-- 算法导论12.2 3题

三、用go语言&#xff0c;写出过程 TREE-PREDECESSOR 的伪代码。 文心一言&#xff1a; 以下是使用Go语言编写的TREE-PREDECESSOR函数的伪代码&#xff1a; func TREE-PREDECESSOR(node) { if node.parent ! nil { return node.parent } // 如果节点是根节点&#xff0c…

TDA4VM EVM开发板调试笔记

文章目录 1. 前言2. 官网资料导读3. 安装 Linux SDK4. 制作SD 启动卡5. 验证启动1. 前言 TDA4作为一般经典的车规级SOC芯片,基于它的低阶智驾方案目前成为各家智驾方案公司的量产首选,这也使得基于TDA4的开发需求陡增,开发和使用TDA4既要熟悉Linux驱应用开发,还要熟悉传统…

「计算机网络」Cisco Packet Tracker计算机网络仿真器的使用

介绍 Cisco Packet Tracker&#xff1a;网络仿真工具&#xff0c;用于模拟网络配置。 &#xff08;一&#xff09; 配置交换机&#xff08;Switch&#xff09;&#xff08;通过 带外管理&#xff09; 带外&#xff1a;Out-of-Band, OOB写在前面&#xff1a;如何打开Console页…

数据结构与算法-动态查找表

查找 &#x1f388;3动态查找表&#x1f52d;3.1二叉排序树&#x1f3c6;3.1.1二叉排序树的类定义&#x1f3c6;3.1.2二叉排序树的插入和生成&#x1f3c6;3.1.3二叉树的查找&#x1f3c6;3.1.4二叉排序树的删除 &#x1f52d;3.2平衡二叉树&#x1f3c6;3.2.1平衡二叉树的调整…