【LeetCode】117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II
难度:中等
题目
给定一个二叉树:
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。
初始状态下,所有 next 指针都被设置为 NULL 。
示例 1:

输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。
示例 2:
输入:root = []
输出:[]
提示:
- 树中的节点数在范围
[0, 6000]内 -100 <= Node.val <= 100
进阶:
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度
个人题解
思路:
- 考虑逐层遍历,考虑用一个list来充当层的概念,每次遍历当前层的时候,把下一层的节点先装到list中
- 则当list中没有节点时,表示所有节点遍历完毕;有节点则继续遍历,遍历时用一个指针完成next的赋值,将当前层节点串起来
class Solution {
public Node connect(Node root) {if (root == null) {return null;}ArrayList<Node> list = new ArrayList<>();list.add(root);while (!list.isEmpty()) {ArrayList<Node> nextList = new ArrayList<>(); // 记录下一层遍历的节点Node curNode = null; // 用于连接for (Node node : list) {if (node.left != null) {nextList.add(node.left);if (curNode != null) {curNode.next = node.left;}curNode = node.left;}if (node.right != null) {nextList.add(node.right);if (curNode != null) {curNode.next = node.right;}curNode = node.right;}}list = nextList;}return root;}
}
进阶:
- 上面层的概念是用list来表示的,分析一下,
- 如果用一个指针指向下一层的头节点,即可得到每层遍历的起点
- 再考虑用一个尾指针表示下一层的尾节点,则遍历当前层时即可将下一层的节点接在尾节点上
- 经过上述分析,遍历过程不再需要list容器,只需要3个指针即可,当前层遍历指针,下一层头指针及下一层尾指针
- 每次遍历完当前层,将下一层头指针及尾指针重置
class Solution {public Node connect(Node root) {Node curTail = root;Node nextHead = null;Node nextTail = null;while (curTail != null) {// 看左子结点if (curTail.left != null) {if (nextTail != null) {nextTail.next = curTail.left;} else {nextHead = curTail.left;}nextTail = curTail.left;}// 看右子结点if (curTail.right != null) {if (nextTail != null) {nextTail.next = curTail.right;} else {nextHead = curTail.right;}nextTail = curTail.right;}if (curTail.next != null) {// 继续当前层遍历curTail = curTail.next;} else {// 当前层遍历完毕,开启下一层遍历,将下一层指针重置curTail = nextHead;nextHead = null;nextTail = null;}}return root;}
}
其他非官方题解:
class Solution {public Node connect(Node root) {Node cur = root;while (cur != null) {Node dummy = new Node(0);Node p = dummy;while (cur != null) {if (cur.left != null) {p.next = cur.left;p = p.next;}if (cur.right != null) {p.next = cur.right;p = p.next;}cur = cur.next;}cur = dummy.next;}return root;}
}
相关文章:
【LeetCode】117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II 难度:中等 题目 给定一个二叉树: struct Node {int val;Node *left;Node *right;Node *next; }填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,…...
《研发效能(DevOps)工程师》课程简介(三)丨IDCF
在研发效能领域中,【开发与交付】的学习重点在于掌握高效的开发工具和框架,了解敏捷开发方法,掌握持续集成与持续交付技术,以及如何保证应用程序的安全性和合规性等方面。 由国家工业和信息化部教育与考试中心颁发的职业技术证书…...
主动激活木马加密流量分析
概述 在网络攻击中,木马病毒通常会使用监听某个端口的方式,或者直接连接C2地址、域名的方式来建立通信,完成命令与控制。而APT攻击中,攻击者为了更高级的潜伏隐蔽需求,其部署的木马或后门,会采用对网卡流量…...
关于单片机CPU如何控制相关引脚
目录 1、相关的单片机结构 2、通过LED的实例解释 1、相关的单片机结构 在寄存器中每一块都有一根导线与引脚对应,通过cpu改变寄存器内的数据(0或1),通过驱动器来控制对于的引脚。 2、通过LED的实例解释 如图所示,芯片…...
[概述] 获取点云数据的仪器
这里所说的获取点云的仪器指的是可以获取场景中物体距离信息的相关设备,下面分别从测距原理以及适用场景来进行介绍。 一、三角测距法 三角测距原理 就是利用三角形的几何关系来测量物体的距离。想象一下,你站在一个地方,你的朋友站在另一…...
路由器基础(八):策略路由配置
在实际网络应用中,策略路由也是一种重要的技术手段。尽管 在考试并不注重策略路由,但是实际上应用较多,建议考生除了掌握基本的静态路由协议IP route-static, 动态路由协议RIP 、OSPF的基础配置外,还要掌握如何配置策略路由。…...
Java 零碎知识点
目录 [多线程]创建多线程的三种方式 [网络编程]一、重点概念1、TCP/IP网络模型2、IP 对象3、端口号4、协议UDP(User Datagram Protocol)TCP(Transmission Control Protocol) 二、UDP 通信三、TCP 通信 [前端][Vue]一、Vue3项目创建响应式函数父子通信父传子子传父 跨层组件通信…...
多模态论文阅读之BLIP
BLIP泛读 TitleMotivationContributionModel Title BLIP: Bootstrapping Language-Image Pre-training for Unified Vision-Language Understanding and Generation Motivation 模型角度:clip albef等要么采用encoder-base model 要么采用encoder-decoder model.…...
OpenCV实战——OpenCV.js介绍
OpenCV实战——OpenCV.js介绍 0. 前言1. OpenCV.js 简介2. 网页编写3. 调用 OpenCV.js 库4. 完整代码相关链接 0. 前言 本节介绍如何使用 JavaScript 通过 OpenCV 开发计算机视觉算法。在 OpenCV.js 之前,如果想要在 Web 上执行一些计算机视觉任务,必须…...
qt5工程打包成可执行exe程序
一、编译生成.exe 1.1、在release模式下编译生成.exe 1.2、建一个空白文件夹package,再将在release模式下生成的.exe文件复制到新建的文件夹中package。 1.3、打开QT5的命令行 1.4、用命令行进入新建文件夹package,使用windeployqt对生成的exe文件进行动…...
Qt之基于QCustomPlot绘制直方图(Histogram),叠加正态分布曲线
一.效果 二.原理 1.正态分布 高斯分布(Gaussian distribution),又名正态分布(Normal distribution),也称"常态分布",也就是说,在正常的状态下,一般的事物,都会符合这样的分布规律。 比如人的身高为一个随机变量,特别高的人比较少,特别矮的也很少,大部分都…...
232.用栈实现队列
原题链接:232.用栈实现队列 思路 主要是要注意栈和队列的数据结构的区别,一个是后进先出, 一个是先进先出 如果要用栈模拟队列的先进先出,那就得使用另一个辅助空间来存储栈的栈顶元素,然后把栈最底部的元素弹出&…...
C51--项目--感应开关盖垃圾桶
1、项目概述 功能描述: 检测靠近时,垃圾桶自动开盖并伴随滴一声,2s后关盖。 发生震动时,垃圾桶自动开盖并伴随滴一声,2s后关盖。 按下按键时,垃圾桶自动开盖并伴随滴一声,2s后关盖。 硬件说明…...
基于单片机设计的太阳能跟踪器
一、前言 随着对可再生能源的需求不断增长,太阳能作为一种清洁、可持续的能源形式,受到越来越多的关注和应用。太阳能光板通常固定在一个固定的角度上,这限制了它们对太阳光的接收效率。为了充分利用太阳能资源,提高太阳能光板的…...
【踩坑及思考】浏览器存储 cookie 最大值超过 4kb,或 http 头 cookie 超过限制值
背景 本地生产环境:超过最大值 cookie token 不存储;客户生产环境:打开系统空白,且控制台报 http 400 错误; 出现了两种现象 现象一:浏览器对大于 4kb 的 cookie 值不存储 导致用户名密码登录ÿ…...
竞赛选题 深度学习实现行人重识别 - python opencv yolo Reid
文章目录 0 前言1 课题背景2 效果展示3 行人检测4 行人重识别5 其他工具6 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 **基于深度学习的行人重识别算法研究与实现 ** 该项目较为新颖,适合作为竞赛课题方向,…...
SpringCloud Gateway实现请求解密和响应加密
文章目录 前言正文一、项目简介二、核心代码2.1 自定义过滤器2.2 网关配置2.3 自定义配置类2.4 加密组件接口2.5 加密组件实现,AES算法2.6 启动类,校验支持的算法配置 三、请求报文示例四、测试结果4.1 网关项目启动时4.2 发生请求时 前言 本文环境使用比…...
IDEA创建Springboot多模块项目
一、创建父模块 File --> New --> Project ,选择 “ Spring Initalizr ” ,点击 Next Next Next --> Finish 二、创建子模块 右键根目录,New --> Module 选择 “ Spring Initializr ”,点击Next 此处注意T…...
React:JSX语法入门
JSX语法入门及代码 JSX是一种JavaScript的语法扩展,用于在React中描述用户界面的结构。它允许开发者使用类似HTML的语法来创建React元素,使得代码更具可读性和可维护性。JSX将HTML标签和JavaScript代码结合在一起,可以在其中使用JavaScript表…...
AI大模型架构师专家,你会问什么来测试我的水平,如何解答上述问题,学习路径是什么
0. 沈剑老师的大模型产品应用经验: 提示词三步骤: 假如我是xxx专家,你会问什么来测试我的水平;假如你是xxx专家,你会如何解答上述问题;假如你是xxx专家,上述问题的学习路径是什么;…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
