力扣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 = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root
        from collections import deque
        queue = 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 = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        first = root
        while first:
            cur = first
            while cur:  # 遍历每一层的节点
                if cur.left: cur.left.next = cur.right  # 找左节点的next
                if cur.right and cur.next: cur.right.next = cur.next.left  # 找右节点的next
                cur = cur.next # cur同层移动到下一节点
            first = first.left  # 从本层扩展到下一层
        return root

复杂度分析:

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

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

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

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

相关文章

酷开科技以创新为动力用大数据提升品牌认知

在21世纪的今天&#xff0c;我们生活在一个被互联网深深改变的世界。互联网不仅改变了我们的生活方式&#xff0c;也正在改变我们的思维方式和工作方式。而互联网作为一种新的发展趋势&#xff0c;更是为我们提供了无数的机会和无限可能性&#xff0c;从电子商务时代到社交网络…

Spring的配置文件,如何配置端口号,,properties,yml获取配置项等方法,外观模式及其优缺点,日志代表的信息

目录 一、回顾 二.如何配置端口号 配置文件&#xff0c;最重要的目的:解决硬编码问题-代码写死 1.常见配置项 yml获取配置项 多次获取配置项&#xff08;yml会对我们的参数情况&#xff0c;进行的一定类型转换比如数字10&#xff0c;转换成“10”&#xff09; null:使用k…

交易历史记录20231205 记录

昨日回顾&#xff1a; select top 10000 * from dbo.CODEINFO A left join dbo.全部&#xff21;股20231205010101 B ON A.CODE B.代码 left join dbo.全部&#xff21;股20231205CONF D on A.CODED.代码left join dbo.全部&#xff21;股20231205 G on A.CODEG.代码 left…

常见面试题之死锁

定义 死锁就是两个或两个以上的线程在执行过程中&#xff0c;由于竞争资源或者互相通信导致彼此占用对方的锁资源而造成的一种阻塞现象&#xff0c;在没有外界作用下都在等待对方释放锁资源&#xff0c;导致程序无法进行下去。 上代码 public class t9 {public static void m…

MongoDB知识总结

这里写自定义目录标题 MongoDB基本介绍MongoDB基本操作数据库相关集合相关增删改查 MongoDB基本介绍 简单介绍 MongoDB是一个基于分布式文件存储的数据库。由C语言编写。旨在为WEB应用提供可扩展的高性能数据存储解决方案。 MongoDB是一个介于关系数据库和非关系数据库之间的产…

基于 Stereo R-CNN 的自动驾驶 3D 目标检测

论文地址&#xff1a;https://openaccess.thecvf.com/content_CVPR_2019/papers/Li_Stereo_R-CNN_Based_3D_Object_Detection_for_Autonomous_Driving_CVPR_2019_paper.pdf 论文代码&#xff1a;https://github.com/HKUST-Aerial-Robotics/Stereo-RCNN 论文背景 大多数 3D 物…

Failed to connect to github.com port 443 after 21055 ms: Timed out

目前自己使用了梯*子还是会报这样的错误&#xff0c;连接不到的github。 查了一下原因&#xff1a; 是因为这个请求没有走代理。 解决方案&#xff1a; 设置 -> 网络和Internet -> 代理 -> 编辑 记住这个IP和端口 使用以下命令&#xff1a; git config --global h…

TCP实现一对一聊天

一&#xff0c;创建类 二&#xff0c;类 1.ChatSocketServer类 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.net.ServerSocket; import java.net.Socket; import java.util.Sca…

Redis哨兵(sentinel)

文章目录 简介搭建框架具体步骤主要文件参数开始配置 案例分析原有的master挂了 哨兵运行流程和选举原理主观下线客观下线(Objectively Down)选举出领导者哨兵(哨兵中选出兵王) 选新的master使用建议 简介 将某一个从库转换为新主库&#xff0c;继续对外服务将某一个从库转换为…

Apache Flink(七):Apache Flink快速入门 - DataStream BATCH模式

🏡 个人主页:IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主:加入大数据技术讨论群聊,获取更多大数据资料。 🔔 博主个人B栈地址:豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 下面使用Java代码使用DataStream…

HarmonyOS应用开发者高级认证考试答案

一、判断题 云函数打包完成后&#xff0c;需要到AppGallery Connect创建对应函数的触发器才可以在端侧中调用&#xff08;错&#xff09;在column和Row容器组件中&#xff0c;aligntems用于设置子组件在主轴方向上的对齐格式&#xff0c;justifycontent用于设置子组件在交叉轴…

Java异步编程之利器:Guava异步编程实践

第1章&#xff1a;引言 - 为什么要用Guava进行异步编程&#xff1f; 大家好&#xff0c;我是小黑&#xff01;今天咱们要聊的是Guava在异步编程中的应用。首先&#xff0c;让我们搞清楚为什么要用Guava来处理异步任务。在Java的世界里&#xff0c;异步编程是个老话题了&#x…

Android--Jetpack--Databinding详解

不经一番寒彻骨&#xff0c;怎得梅花扑鼻香 一&#xff0c;定义 DataBinding, 又名数据绑定&#xff0c;是Android开发中非常重要的基础技术&#xff0c;它可以将UI组件和数据模型连接起来&#xff0c;使得在数据模型发生变化时&#xff0c;UI组件自动更新。是 MVVM 模式在 An…

Day52力扣打卡

打卡记录 Collapsing Strings&#xff08;Trie树&#xff09; 链接 #include <iostream> #include <algorithm> using namespace std; const int N 2e6 10; int son[N][26], idx, cnt1[N], cnt2[N]; int main() {auto insert [&](string& str, int* c…

计算机基础知识66

Auth的补充 #概念&#xff1a;是django 的一个app&#xff0c;关于用户的登录&#xff0c;退出&#xff0c;注册... # 配置文件中配置&#xff1a;表会被迁移 INSTALLED_APPS [django.contrib.auth,] # auth有哪些表---权限控制&#xff1a; Permission&#xff1a;auth_permi…

【PyTorch】权重衰减

文章目录 1. 理论介绍2. 实例解析2.1. 实例描述2.2. 代码实现 1. 理论介绍 通过对模型过拟合的思考&#xff0c;人们希望能通过某种工具调整模型复杂度&#xff0c;使其达到一个合适的平衡位置。权重衰减&#xff08;又称 L 2 L_2 L2​正则化&#xff09;通过为损失函数添加惩…

HTTPS 的通信加解密过程,证书为什么更安全?

目录 一、什么是https 二、HTTPS 的加解密过程 三、HTTPS 为什么更安全&#xff1f; 一、什么是https HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;是一种通过加密和身份验证保护数据传输安全的通信协议。它是在常用的HTTP协议基础上添加了 SSL/TLS 加…

Memory-augmented Deep Autoencoder for Unsupervised Anomaly Detection 论文阅读

Memorizing Normality to Detect Anomaly: Memory-augmented Deep Autoencoder for Unsupervised Anomaly Detection 摘要1.介绍2.相关工作异常检测Memory networks 3. Memory-augmented Autoencoder3.1概述3.2. Encoder and Decoder3.3. Memory Module with Attention-based S…

redis中使用事务

事务是指一个执行过程&#xff0c;要么全部执行成功&#xff0c;要么失败什么都不改变。不会存在一部分成功一部分失败的情况&#xff0c;也就是事务的ACID四大特性&#xff08;原子性、一致性、隔离性、持久性&#xff09;。但是redis中的事务并不是严格意义上的事务&#xff…

论MYSQL注入的入门注解

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 &#x1f4d1;什么是MySQL注入&…