当前位置: 首页 > news >正文

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

2哥 : 3妹,听说你昨天去面试了,怎么样啊?
3妹:嗨,别提了,让我回去等通知,估计是没有通知了, 还浪费我请了一天假。
2哥 : 你又请假了啊, 你是怎么跟你那个严厉的老板请假的。
3妹:我说我2哥生病了,嘿嘿~
偷笑

2哥:一猜就是说我生病了,自从你找工作,我这一年都病了十几回了……
3妹:没办法,假不好请嘛, 我尽快找到工作,让你的病快点好。
2哥:你就不能盼我点好,你可以说你2哥结婚了嘛
3妹:对哦,这个理由可以下次说。 不过2哥,你还是个单身狗耶, 要赶紧给我找个2嫂了哈~
2哥:去去,不跟你说了,再给你出道题,兴许下次面试会遇到:

题目:

给定一个二叉树:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。

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

示例 1:
image.png
输入: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
进阶:

你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。

思路:

思考

层次遍历。树的层次遍历基于广度优先搜索,它按照层的顺序遍历二叉树,在遍历第 i层前,一定会遍历完第 i−1 层。

算法如下:初始化一个队列 q,将根结点放入队列中。当队列不为空的时候,记录当前队列大小为 n,从队列中以此取出 n 个元素并通过这 n 个元素拓展新节点。如此循环,直到队列为空。

java代码:

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/
class Solution {public Node connect(Node root) {if (root == null) {return null;}Queue<Node> queue = new ArrayDeque<Node>();queue.offer(root);while (!queue.isEmpty()) {int n = queue.size();Node last = null;for (int i = 1; i <= n; ++i) {Node f = queue.poll();if (f.left != null) {queue.offer(f.left);}if (f.right != null) {queue.offer(f.right);}if (i != 1) {last.next = f;}last = f;}}return root;}
}

相关文章:

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

2哥 : 3妹&#xff0c;听说你昨天去面试了&#xff0c;怎么样啊&#xff1f; 3妹&#xff1a;嗨&#xff0c;别提了&#xff0c;让我回去等通知&#xff0c;估计是没有通知了&#xff0c; 还浪费我请了一天假。 2哥 : 你又请假了啊&#xff0c; 你是怎么跟你那个严厉的老板请假…...

window10 mysql8.0 修改端口port不生效

mysql的默认端口是3306&#xff0c;我想修改成3307。 查了一下资料&#xff0c;基本上都是说先进入C:\Program Files\MySQL\MySQL Server 8.0这个目录。 看看有没有my.ini&#xff0c;没有就新建。 我这里没有&#xff0c;就新建一个&#xff0c;然后修改port&#xff1a; […...

欧盟网络安全威胁:虚假与错误信息

如今&#xff0c;数字平台已是新闻媒体的主战地。社交网站、新闻媒体、甚至搜索引擎都是现在大多数人的信息来源。由于这些网站的运作方式是通过吸引人们来产生网站流量&#xff0c;这些抓人眼球的信息通常是推广广告&#xff0c;有些甚至没有经过审查。 国际现状 恶意攻击者现…...

006 Linux 进程的概念 | 获取进程的PID

前言 本文将会向您进程的概念&#xff0c;程序与进程的区别&#xff0c;如何获取进程的标识符-pid 文章重点 1.描述进程——PCB 进程与程序的区别 CPU对进程列表的处理 2.获取进程PID 描述进程-PCB 进程概念 课本概念&#xff1a;程序的一个执行实例或正在执行的程序 内核…...

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测 目录 时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 …...

《异常检测——从经典算法到深度学习》23 TimesNet: 用于常规时间序列分析的时间二维变化模型

zz# 《异常检测——从经典算法到深度学习》 0 概论1 基于隔离森林的异常检测算法 2 基于LOF的异常检测算法3 基于One-Class SVM的异常检测算法4 基于高斯概率密度异常检测算法5 Opprentice——异常检测经典算法最终篇6 基于重构概率的 VAE 异常检测7 基于条件VAE异常检测8 Don…...

计算机网络(59)

1. OSI 的七层模型分别是&#xff1f;各自的功能是什么&#xff1f; 2. 为什么需要三次握手&#xff1f;两次不行&#xff1f; 3. 为什么需要四次挥手&#xff1f;三次不行&#xff1f; 4. TCP与UDP有哪些区别&#xff1f;各自应用场景&#xff1f; 5. HTTP1.0&#xff0c;1.1&…...

【CSS】CSS基础知识扫盲

1、 什么是CSS&#xff1f; CSS即层叠样式表 (Cascading Style Sheets). CSS 能够对网页中元素位置的排版进行像素级精确控制, 实现美化页面的效果. 能够做到页面的样式和结构分离 2、 CSS引入方式 CSS代码编写的时候有多种引入方式&#xff1a; 内部样式、外部样式、内联样…...

React中的状态管理

目录 前言 1. React中的状态管理 1.1 本地状态管理 1.2 全局状态管理 Redux React Context 2. React状态管理的优势 总结 前言 当谈到前端开发中的状态管理时&#xff0c;React是一个备受推崇的选择。React的状态管理机制被广泛应用于构建大型、复杂的应用程序&#xf…...

【优选算法系列】【专题九链表】第一节.链表常用技巧和操作总结(2. 两数相加)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、链表常用技巧和操作总结二、两数相加 2.1 题目描述 2.2 题目解析 2.2.1 算法原理 2.2.2 代码编写总结 前言 一、链表常…...

上线Spring boot-若依项目

基础环境 所有环境皆关闭防火墙与selinux 服务器功能主机IP主机名服务名称配置前端服务器192.168.231.177nginxnginx1C2G后端服务器代码打包192.168.231.178javajava、maven、nodejs4C8G数据库/缓存192.168.231.179dbmysql、redis2C4G Nginx #配置Nginxyum源 [rootnginx ~]…...

pinia简单使用

新命令-创建vue3项目 vue create 方式使用脚手架创建项目&#xff0c;vue cli处理&#xff0c; vue3后新的脚手架工具create-vue 使用npm init vuelatest 命令创建即可。 在pinia中&#xff0c;将使用的组合式函数识别为状态管理内容 自动将ref 识别为stste,computed 相当于 ge…...

数据库进阶教学——数据库故障恢复(日志文件)

目录 一、日志简介 二、日志文件操作 1、查看日志状态 2、开启日志功能 3、查看日志文件 4、查看当前日志 5、查看日志中的事件 6、删除日志文件 7、查看和修改日志文件有效期 8、查看日志文件详细信息 三、删除的数据库恢复 一、日志简介 日志是记录所有数据库表结…...

Leetcode 73 矩阵置0

class Solution {//1.用矩阵的第一行和第一列来标记该行或该列是否应该为0,但是这样的话忽视了第一行或第一列为0的情况//2.用标记row0和column0来标记第一行或第一列是否该为0public void setZeroes(int[][] matrix) {int n matrix.length;int m matrix[0].length;boolean r…...

Rust学习日记(二)变量的使用--结合--温度换算/斐波那契数列--实例

前言&#xff1a; 这是一个系列的学习笔记&#xff0c;会将笔者学习Rust语言的心得记录。 当然&#xff0c;这并非是流水账似的记录&#xff0c;而是结合实际程序项目的记录&#xff0c;如果你也对Rust感兴趣&#xff0c;那么我们可以一起交流探讨&#xff0c;使用Rust来构建程…...

html各个标签的使用

一、标签的分类 1、单标签和双标签 1. 单标签&#xff1a;<img> img br hr 2. 双标签&#xff1a;<div></div> div span <a></a> h p a 2、按照标签属性分类 1. 块标签&#xff1a;自己独占一行 h1~h6 p div 2. 行内(内联)标签 …...

android 混淆

# 指定代码的压缩级别 0 - 7(指定代码进行迭代优化的次数&#xff0c;在Android里面默认是5&#xff0c;这条指令也只有在可以优化时起作用。) -optimizationpasses 5 # 混淆时不会产生形形色色的类名(混淆时不使用大小写混合类名) -dontusemixedcaseclassnames # 指定不去忽略…...

旋转链表(C++解法)

题目 给你一个链表的头节点 head &#xff0c;旋转链表&#xff0c;将链表每个节点向右移动 k 个位置。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], k 2 输出&#xff1a;[4,5,1,2,3]示例 2&#xff1a; 输入&#xff1a;head [0,1,2], k 4 输出&#xff1a;[…...

AcWing 134:双端队列

【题目来源】https://www.acwing.com/problem/content/description/136/【题目描述】 达达现在碰到了一个棘手的问题&#xff0c;有 N 个整数需要排序。 达达手头能用的工具就是若干个双端队列。 她从 1 到 N 需要依次处理这 N 个数&#xff0c;对于每个数&#xff0c;达达能做…...

Spring Cloud Gateway 重写 URL

目录 1、简介 2、Spring Cloud Gateway 快速回顾 3、基于配置的 URL 重写 4、基于 DSL 的 URL 重写 5、测试 6、总结 1、简介 Spring Cloud Gateway 的常见用例是作为一个网关&#xff0c;代理一个或多个服务&#xff0c;从而为客户端提供更简单的消费方式。 本文将带你…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...