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

leetcode 116. 填充每个节点的下一个右侧节点指针

leetcode 116. 填充每个节点的下一个右侧节点指针

题目

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

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

初始状态下,所有 next 指针都被设置为 NULL。
在这里插入图片描述

思路

这道题假设用层序遍历开一个队列来做其实非常的简单,但是他既然说了进阶要不开额外空间,这一点就值得考量了。实际上就是怎样才能去掉这个队列呢,那就必然得拿到下一个节点,这个可以借助父节点的next来做,因为遍历到下一层的时候,父节点的next是已知的。所以就一目了然了,这道题除了迭代外,还可以用递归。

代码

// 迭代
/*
// 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 root;}// Deque<Node> queue = new ArrayDeque<Node>();// queue.offerLast(root);Node node = root;while (node.left != null) {Node firstnode = node;while (node != null) {if (node.left != null) {node.left.next = node.right;}if (node.next != null) {node.right.next = node.next.left;}node = node.next;}node = firstnode.left;}return root;}
}
// 递归
/*
// 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;}if (root.left != null) {root.left.next = root.right;root.right.next = root.next == null ? null : root.next.left;connect(root.left);connect(root.right);}return root;}
}

相关文章:

leetcode 116. 填充每个节点的下一个右侧节点指针

leetcode 116. 填充每个节点的下一个右侧节点指针 题目 给定一个 完美二叉树 &#xff0c;其所有叶子节点都在同一层&#xff0c;每个父节点都有两个子节点。二叉树定义如下&#xff1a; struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next …...

[C++]优先级队列

1 .了解优先级队列 优先级队列是一种容器适配器&#xff0c;根据一些严格的弱排序标准&#xff0c;专门设计使其第一个元素始终是它所包含的元素中最大的元素。 此上下文类似于堆&#xff0c;其中可以随时插入元素&#xff0c;并且只能检索最大堆元素&#xff08;优先级队列中顶…...

学习大数据DAY22 Linux 基 本 指 令 3与 在 Linux 系 统 中 配 置MySQL 和 Oracle

目录 网络配置类 ps 显示系统执行的进程 kill systemctl 服务管理 配置静态 ip 常见错误---虚拟机重启网卡失败或者网卡丢失 mysql 操作 上机练习 6---安装 mysql---参考《mysql 安装》文档 解锁 scott 重启后的步骤 上机练习 7---安装 oracle---参考《oracle 安装》…...

scp 服务器复制命令

步骤如下&#xff1a; 终端执行如下命令 #ssh-keygen -t rsa 2. 密钥生成后会在 /root/.ssh/ 文件夹下产生两个文件 id_rsa id_rsa.pub 将 id_rsa.pub 文件复制到 152.136.121.24 执行如下命令 scp /root/.ssh/id_rsa.pub root152.136.121.24:/root/.ssh/authorized_keys…...

PyQt5学习路线

后续会根据该文章的路线逐步发布对应的教程&#xff0c;订阅专栏不迷路&#x1f970; 本专栏纯干货&#x1f929; 学习Python的PyQt5库&#xff0c;可以遵循以下的学习路线&#xff1a; 1. Python基础 掌握Python语法&#xff1a;确保你熟悉Python的基本语法&#xff0c;包括…...

2024论文精读:利用大语言模型(GPT)增强上下文学习去做关系抽取任务

文章目录 1. 前置知识2. 文章通过什么来引出他要解决的问题3. 作者通过什么提出RE任务存在上面所提出的那几个问题3.1 问题一&#xff1a;ICL检索到的**示范**中实体个关系的相关性很低。3.2 问题二&#xff1a;示范中缺乏解释输入-标签映射导致ICL效果不佳。 4. 作者为了解决上…...

WEB 手柄 http通信,mcu端解析代码 2024/7/23 日志

WEB 手柄 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>WEB遥控器</title> </head> &l…...

cmake中的正则表达式

以下字符或者字符组合在cmake的正则表达式中的特殊含义&#xff1a; ^ 匹配输入的开始 $ 匹配输入的结束 . 匹配任意一个字符 \<char> 匹配一个字符&#xff0c;如.匹配字符.&#xff0c;\匹配字符\&#xff0c;\a匹配字符a [ ] 匹配在括号里面的任意字符&#xff0…...

05. Java 三大范式

1. 前言 在面向对象语言中涉及到诸多的设计模式&#xff0c;例如单例模式、适配器模式&#xff0c;设计模式的存在是为了让系统中的代码逻辑更加清晰&#xff0c;帮助开发者建立更加健壮的系统&#xff0c;同时满足易修改特性和易扩展特性。数据库设计时也存在类似设计模式的通…...

opencv 按键开启连续截图,并加载提示图片

背景图小图 键盘监听使用的是pynput 库 保存图片时使用了年月日时分秒命名 原图&#xff1a; from pynput import keyboard import cv2 import time# 键盘监听 def on_press(key):global jieglobal guanif key.char a:jie Trueelif key.char d:jie Falseelif key.char…...

Android-- 集成谷歌地图

引言 项目需求需要在谷歌地图&#xff1a; 地图展示&#xff0c;设备点聚合&#xff0c;设备站点&#xff0c;绘制点和区域等功能。 我只针对我涉及到的技术做一下总结&#xff0c;希望能帮到开始接触谷歌地图的伙伴们。 集成步骤 1、在项目的modle的build.gradle中添加依赖如…...

Jvm是如何处理异常的

异常抛出 当Java程序运行时遇到无法处理的情况时,会抛出一个异常(比如在一个方法中如果发生异常),这时会创建一个异常对象,并转交给JVM,该异常对象包含异常名称,异常描述以及异常发生时应用程序的状态。创建异常对象并转交给JVM的过程称为抛出异常。 异常捕捉 当JVM检测…...

recursion depth exceeded” error

有些时候不可以用jax.jit装饰器 参考资料&#xff1a;使用 JAX 后端在 Keras 3 中训练 GAN |由 Khawaja Abaid |中等 (medium.com)...

虚拟现实和增强现实技术系列—Expressive Talking Avatars

文章目录 1. 概述2. 背景介绍3. 数据集3.1 设计标准3.2 数据采集 4. 方法4.1 概述4.2 架构4.3 目标函数 5. 实验评测5.1 用户研究5.2 我们方法的结果5.3 比较与消融研究 1. 概述 支持远程协作者之间的交互和沟通。然而&#xff0c;明确的表达是出了名的难以创建&#xff0c;主…...

网站验证:确保网络安全与信任的重要步骤

网站验证&#xff1a;确保网络安全与信任的重要步骤 引言 在数字时代&#xff0c;网站验证是确保网络安全和建立用户信任的关键措施。随着网络诈骗和恶意软件的日益增多&#xff0c;验证网站的真实性和安全性变得尤为重要。本文将探讨网站验证的重要性、常见的验证方法以及如…...

C语言——字符串比较函数strcmp和strncmp

目录 strcmp 函数原型如下&#xff1a; 示例 注意事项 strcmp自实现代码&#xff1a; strncmp 函数 函数原型&#xff1a; 参数&#xff1a; 返回值&#xff1a; 特点&#xff1a; 两者之间的区别和联系 strcmp strcmp 是 C 语言标准库中的一个函数&#xff0c;用于…...

redis的集群模式

目录 1. 为什么使用redis集群 2. 主从模式 2.1修改配置文件 2.2 开启三台redis服务 2.3配置主从关系 3. 哨兵模式 3.1 监控功能 3.2 选举的机制 3.3 准备条件 4. 去中心化模式 4.1 准备三主三从 4.2 启动redis 4.3 分配槽以及主从关系 4.4 命令行的客户端 redis提供…...

基于微信小程序+SpringBoot+Vue的青少年科普教学系统平台(带1w+文档)

基于微信小程序SpringBootVue的青少年科普教学系统平台(带1w文档) 基于微信小程序SpringBootVue的青少年科普教学系统平台(带1w文档) 这个工具就是解决上述问题的最好的解决方案。它不仅可以实时完成信息处理&#xff0c;还缩短高校教师成果信息管理流程&#xff0c;使其系统化…...

智能听觉:从任务特定的机器学习到基础模型

关键词&#xff1a;计算机听觉、音频基础模型、多模态学习、声音事件检测 声音无处不在&#xff0c;弥漫于我们生活的每一个角落。鸟儿向伴侣倾诉心意的歌声&#xff0c;浓缩咖啡机中蒸汽的嘶嘶作响&#xff0c;午后阳光下昆虫振翅的嗡嗡声&#xff0c;金属屋顶上雨滴跳跃的滴答…...

14、如何⽤DDD设计微服务代码模型

在完成领域模型设计后&#xff0c;接下来我们就可以开始微服务的设计和 落地了。在微服务落地前&#xff0c;⾸先要确定微服务的代码结构&#xff0c;也就是我 下⾯要讲的微服务代码模型。 只有建⽴了标准的微服务代码模型和代码规范后&#xff0c;我们才可以将 领域对象映射到…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...