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

LeetCode算法二叉树—116. 填充每个节点的下一个右侧节点指针

目录

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

题解:

代码:

运行结果:


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

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 = []
输出:[]

提示:

  • 树中节点的数量在 [0, 212 - 1] 范围内
  • -1000 <= node.val <= 1000

进阶:

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

迭代解法题解:

    // 迭代解决:仔细观察发现有两种连接方式

    // 1、两个连接点有共同父节点

    // 2、两个连接点父节点不同,分别是一个节点和上一层邻居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 {// 迭代解决:仔细观察发现有两种连接方式// 1、两个连接点有共同父节点// 2、两个连接点父节点不同,分别是一个节点和上一层邻居next的左节点// 我们可以根据当前节点处理他的子节点,相当于一层一层处理// 所以需要两个循环嵌套,里面的横向处理完该层,再竖向进入下一层public Node connect(Node root) {// 特判:无节点则不需处理if(root==null) return root;// 定义一个节点等于rootNode pre=root;// 左节点不为空则这层需要处理,进入循环开始处理这一层while(pre.left!=null){Node tmp=pre;while(tmp!=null){// 处理有共同父节点的连接点tmp.left.next=tmp.right;// 处理父节点不同的连接点if(tmp.next!=null){tmp.right.next=tmp.next.left;}// 横向移动处理这一层未处理的节点tmp=tmp.next;}// 竖向移动处理下一层pre=pre.left;}return root;}
}

运行结果:

相关文章:

LeetCode算法二叉树—116. 填充每个节点的下一个右侧节点指针

目录 116. 填充每个节点的下一个右侧节点指针 题解&#xff1a; 代码&#xff1a; 运行结果&#xff1a; 给定一个 完美二叉树 &#xff0c;其所有叶子节点都在同一层&#xff0c;每个父节点都有两个子节点。二叉树定义如下&#xff1a; struct Node {int val;Node *left;N…...

二、2023.9.28.C++基础endC++内存end.2

文章目录 17、说说new和malloc的区别&#xff0c;各自底层实现原理。18、 说说const和define的区别。19、 说说C中函数指针和指针函数的区别&#xff1f;20、 说说const int *a, int const *a, const int a, int *const a, const int *const a分别是什么&#xff0c;有什么特点…...

DevSecOps 将会嵌入 DevOps

通常人们在一个项目行将结束时才会考虑到安全&#xff0c;这么做会导致很多问题&#xff1b;将安全融入到DevOps的工作流中已产生了积极结果。 DevSecOps&#xff1a;安全正当时 一直以来&#xff0c;开发人员在构建软件时认为功能需求优先于安全。虽然安全编码实践起着重要作…...

不同管径地下管线的地质雷达响应特征分析

不同管径地下管线的地质雷达响应特征分析 前言 以混凝土管线为例&#xff0c;建立了不同管径的城市地下管线模型&#xff0c;进行二维地质雷达正演模拟&#xff0c;分析不同管径管线的地质雷达响应特征。 文章目录 不同管径地下管线的地质雷达响应特征分析前言1、管径50cm2、…...

【接口测试学习】白盒测试 接口测试 自动化测试

一、什么是白盒测试 白盒测试是一种测试策略&#xff0c;这种策略允许我们检查程序的内部结构&#xff0c;对程序的逻辑结构进行检查&#xff0c;从中获取测试数据。白盒测试的对象基本是源程序&#xff0c;所以它又称为结构测试或逻辑驱动测试&#xff0c;白盒测试方法一般分为…...

7.网络原理之TCP_IP(下)

文章目录 4.传输层重点协议4.1TCP协议4.1.1TCP协议段格式4.1.2TCP原理4.1.2.1确认应答机制 ACK&#xff08;安全机制&#xff09;4.1.2.2超时重传机制&#xff08;安全机制&#xff09;4.1.2.3连接管理机制&#xff08;安全机制&#xff09;4.1.2.4滑动窗口&#xff08;效率机制…...

Docker Dockerfile解析

Dockerfile是什么 Dockerfile是用来构建Docker镜像的文本文件&#xff0c;是由一条条构建镜像所需的指令和参数构成的脚本。 官网&#xff1a;Dockerfile reference | Docker Docs 构建三步骤&#xff1a; 编写Dockerfile文件docker build命令构建镜像docker run依镜像运行容…...

浏览器从输入URL到页面展示这个过程中都经历了什么

一. URL输入 URL是统一资源定位符&#xff0c;用于定位互联网上的资源&#xff0c;俗称网址。我们在地址栏输入网址后敲下回车&#xff0c;浏览器会对输入的信息进行以下判断&#xff1a; 1. 检查输入的内容是否是一个合法的URL连接 2. 如果合法的话&#xff0c;则会判断URL…...

2023-09-22 monetdb-事务管理-乐观并发控制-记录

摘要: 2023-09-22 monetdb-事务管理-记录 相关文档: Transaction Management | MonetDB Docs https://en.wikipedia.org/wiki/Optimistic_concurrency_control monetdb事务管理: MonetDB/SQL 支持以 START TRANSACTION 标记并以 COMMIT 或 ROLLBACK 关闭的多语句事务方案。如果…...

蓝桥等考Python组别四级008

第一部分:选择题 1、Python L4 (15分) 字符“D”的ASCII码值比字符“F”的ASCII码值小( )。 1234正确答案:B 2、Python L4 (15分) 下面的Python变量名正…...

SpringMVC 学习(二)Hello SpringMVC

3. Hello SpringMVC (1) 新建 maven 模块 springmvc-02-hellomvc (2) 确认依赖的导入 (3) 配置 web.xml <!--web/WEB-INF/web.xml--> <?xml version"1.0" encoding"UTF-8"?> <web-app xmlns"http://xmlns.jcp.org/xml/ns/javaee…...

交换机之间配置手动|静态链路聚合

两台交换机&#xff0c;配置链路聚合&#xff1a; 1、禁止自动协商速率&#xff0c;配置固定速率 int G0/0/1 undo negotiation auto speed 100int G0/0/2 undo negotiation auto speed 100 2、配置eth-trunk int eth-trunk 1 mode manual | lacp-staticint G0/0/1 eth-trun…...

Shiro高级及SaaS-HRM的认证授权

Shiro在SpringBoot工程的应用 Apache Shiro是一个功能强大、灵活的&#xff0c;开源的安全框架。它可以干净利落地处理身份验证、授权、企业会话管理和加密。越来越多的企业使用Shiro作为项目的安全框架&#xff0c;保证项目的平稳运行。 在之前的讲解中只是单独的使用shiro&…...

eclipse svn插件安装

1.进入eclipse的help->Eclipse Marketplace,如下图所示&#xff1a; 2.输入“svn”,再按回车&#xff0c;如下图&#xff1a; 3.这我选择的是 Subversive,点击后面的“install”按钮&#xff0c;如下图 Eclipse 下连接 SVN 库有两种插件 —— Subclipse 与 Subversive &…...

C语言 cortex-A7核 UART总线 实验

一、C 1&#xff09;uart4.h #ifndef __UART4_H__ #define __UART4_H__ #include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_uart.h&quo…...

不同走向地下管线的地质雷达响应特征分析

不同走向地下管线的地质雷达响应特征分析 前言 以PVC管线为例&#xff0c;建立不同走向&#xff08;水平倾斜、垂直倾斜、水平相邻&#xff09;的三维管线地质模型&#xff0c;进行三维地质雷达数据模拟&#xff0c;分析不同走向地下管线的地质雷达响应特征。 文章目录 不同…...

Nginx负载均衡详解

一、负载均衡介绍 1、负载均衡的定义 单体服务器解决不了并发量大的请求&#xff0c;所以&#xff0c;我们可以横向增加服务器的数量&#xff08;集群&#xff09;&#xff0c;然后将请求分发到各个服务器上&#xff0c;将原先请求集中到单个服务器上的情况改为将请求分发到多…...

基于Spring Boot的宠物咖啡馆平台的设计与实现

目录 前言 一、技术栈 二、系统功能介绍 用户信息管理 看护师信息管理 宠物寄养管理 健康状况管理 点单 宠物体验 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已…...

TYVJ P1026 犁田机器人

描述 Farmer John為了让自己从无穷无尽的犁田工作中解放出来&#xff0c;於是买了个新机器人帮助他犁田。这个机器人可以完成犁田的任务&#xff0c;可惜有一个小小的缺点&#xff1a;这个犁田机器人一次只能犁一个边的长度是整数的长方形的田地。 因為FJ的田地有树和其他障碍…...

软件测试面试经验分享,真实面试题

前言 本人普通本科计算机专业&#xff0c;做测试也有3年的时间了&#xff0c;讲下我的经历&#xff0c;我刚毕业就进了一个小自研薪资还不错&#xff0c;有10.5k&#xff08;个人觉得我很优秀&#xff09;&#xff0c;在里面呆了两年&#xff0c;积累了一些的经验和技能&#…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...