二叉树:填充每个节点的下一个右侧节点指针(java)
leetcode116:填充每个节点的下一个右侧节点指针
- leetcode原题链接:
- 题目描述
- 递归解法一
- 递归方法二(效率更高)
- 二叉树专题
leetcode原题链接:
116题:填充每个节点的下一个右侧节点指针
题目描述
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
输入: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
进阶:
你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
递归解法一
解题思路:
这题在递归中,主要思考点就是,递归左树和右树时。不是同一个头节点的子树时,怎么样把左树链接到右树上去。如上图中五和六节点在递归过程中,这两个点,并没在同一个递归过程中。就无法链接起来,因此我们要修改下递归过程,把左右树同时递归,这样在同一个过程里,就可以看见兄弟节点了。代码演示如下。
public Node connect(Node root) {if(root == null){return root;}process(root.left,root.right);return root;}public void process(Node root1,Node root2){if(root1 == null || root2 == null){return ;}root1.next = root2;//左树内部链接起来。process(root1.left,root1.right);//右树内部链接起来process(root2.left,root2.right);//左树和右树链接起来。process(root1.right,root2.left);}
递归方法二(效率更高)
思路:
我们在递归的过程中,把层级结构也进行递归,每次把层级结构和左树的右节点放进map 中,在遍历到右树时,根据层级来判断,拿到左树,然后把它们相连,就完成了递归。和上面相比,少了一次递归。效率会增加很多.代码演示。
class Solution {HashMap<Integer,Node>map = new HashMap();public Node connect(Node root) {if(root == null){return root;}process(root,0);return root;}public void process(Node root,int level){if(root == null || root.left == null){return;}root.left.next = root.right;v6(root.left,level + 1);v6(root.right,level + 1);if(map.get(level) != null){Node cur = map.get(level);cur.next = root.left;}map.put(level,root.right);}}
二叉树专题
从前序与中序遍历序列构造二叉树(java)
leetcode二叉树中的最大路径和(java)
二叉树的递归–判断二叉树是否是满二叉树(java实现)
相关文章:
二叉树:填充每个节点的下一个右侧节点指针(java)
leetcode116:填充每个节点的下一个右侧节点指针 leetcode原题链接:题目描述递归解法一递归方法二(效率更高)二叉树专题 leetcode原题链接: 116题:填充每个节点的下一个右侧节点指针 题目描述 给定一个 完美二叉树 &a…...
Android 12.0修改系统默认设备类型的平板电脑类型为设备类型
1.概述 在12.0的系统rom产品开发中,对于产品设备类型都默认为tablet即平板电脑类型,即 product="tablet" 在一些不是平板的项目中,可能需要修改这个类型为device类型 即 product="device",这就需要找到相关设置系统属性的代码,修改系统属性就可以了 2…...
debug研究
debug研究 debug的condition 通常用在for循环里面 for循环中实际使用 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UsmJ93w5-1685344057464)(D:\typora_pic_all\image-20230529145417753.png)] log.info("当前共有{}条数据待处理", vos…...
zabbix监控系统
一、Zabbix概述 1、使用zabbix的原因 作为一个运维,需要会使用监控系统查看服务器状态以及网站流量指标,利用监控系统的数据去了解上线发布的结果,和网站的健康状态。 利用一个优秀的监控软件,我们可以: ●通过一个友好的界面进…...
Python入门学习
一、执行Python(Hello World)程序 对于大多数程序语言,第一个入门编程代码便是 “Hello World!”,以下代码为使用 Python 输出 “Hello World!” 1.1 创建hello.py文件 1.2 编写程序 #!/usr/bin/python…...
自动驾驶嵌入式开发工程师:车载SOC开发修炼秘籍
声明:本文档是博主在开发学习过程中写的笔记,本意是便于以后开发复盘,参考《 ug1144-petalinux-tools-reference-guide》、《ug1085》、黑金Zynq UltraScale MPSoC 5EV开发板资料、英伟达官方资料。大佬勿喷 大佬勿喷 大佬勿喷!&a…...
Linux之搭建环境
文章目录 1 FileZilla软件2 Linux搭建samba文件共享服务器,实现基于Linux和Windows的共享文件服务2.1 smaba的安装与基本应用2.2 samba的账号权限配置2.3 win系统下的文件无法复制到Linux共享文件夹中 1 FileZilla软件 在跟着正点原子教程安装后,出现如下…...
泡利矩阵(一)
〇、厄米矩阵 厄米矩阵(Hermitian Matrix),也称为自共轭矩阵(Self-adjoint Matrix),是线性代数中的一个重要概念。它是指一个复数域上的方阵,其转置矩阵与共轭矩阵相等。 具体来说,…...
通用支付系统设计
支付永远是一个公司的核心领域,因为这是一个有交易属性公司的命脉。那么,支付系统到底长什么样,又是怎么运行交互的呢?抛开带有支付牌照的金融公司的支付架构,下述链路和系统组成基本上符合绝大多数支付场景。其实整体可以看成是…...
metaRTC+ZLMediaKit实现webrtc的推拉流
概述 ZLMediaKit是一个基于C11的高性能运营级流媒体服务框架,是一个支持webrtc SFU的优秀的流媒体服务器系统。 metaRTC新版本支持whip/whep协议,支持whip/whep协议的ZLMediaKit推拉流。 信令通信 ZLMediaKit新版本支持whip和whep协议,支…...
【JavaSE】Java基础语法(八)
文章目录 🍓1. 类和对象🍹🍹1.1 类和对象的关系🍹🍹1.2 类的定义 🍓2. 对象内存图🍹🍹2.1 单个对象内存图🍹🍹2.2 多个对象内存图2.3 多个对象指向相同内存图…...
Java如何配置环境变量
Java如何配置环境变量 0. 前言1. 下载Java2. 配置环境变量2.1新建 Java_Home2.2 编辑Path情况1情况2 3. 验证安装 0. 前言 本节记录如何配置Java环境变量,用自己重装过的系统实操 操作系统:Windows10 专业版 Java版本:jdk1.7.0_07 1. 下载…...
android 12.0SystemUI 状态栏下拉快捷添加截图快捷开关
1.概述 在12.0的系统产品rom定制化开发中,对SystemUI的定制需求也是挺多的,在下拉状态栏中 添加截图快捷开关,也是常有的开发功能,下面就以添加 截图功能为例功能的实现 2.SystemUI 状态栏下拉快捷添加截图快捷开关的核心代码 frameworks/base/packages/SystemUI/res/va…...
【无标题】 Vue 路由库Router 【重点】 - 安装 - 基本使用 - 路由配置 - 路由模式 - 路由传递参数 - 路由内置对象 - 路由守卫
0.0 课程介绍 Vue 路由库Router 【重点】 安装基本使用路由配置路由模式路由传递参数路由内置对象路由守卫 Vue的内置API 【掌握】 ref Vue.set Vue.nextTick Vue.filter Vue.component Vue.use Vue.directive 1.0 Vue的路由Router 【重点】 1.1 路由作用 进行页面…...
RocksDB笔记 -- 整体架构
RocksDB是由Facebook开发的存储引擎, 它最初的目标是用于快速存储, 特别是Flash存储. 一个基于C开发keys-values存储引擎库. 整体架构 RocksDB由这三个基本结构组成: memtable, sstfile 和 logfile. 其中: memtable是一个内存数据结构, 新的写入会插入到memtable中, 同时可选…...
设计模式之单例模式入门介绍
一、设计模式概念 设计模式是被广泛使用的软件开发中的一种解决方案,它提供了一套被验证过的、可重用的设计思想,帮助开发人员更加高效地开发出可维护、易扩展的软件系统。 设计模式可以分为三类:创建型模式、结构型模式和行为型模式。 1.1…...
RHCE 作业三
1.基于域名访问网站 [rootserver ~]# setenforce 0 [rootserver ~]# systemctl stop firewalld [rootserver ~]# systemctl disable firewalld [rootserver ~]# yum install httpd -y [rootserver ~]# systemctl start httpd [rootserver ~]# syst…...
90.qt qml-Table表格组件(支持表头表尾固定/自定义颜色/自定义操作按钮/插入排序)
众所周知,qml table在目前版本还很废,qt5的table完全就没法用,在之前章节就写过: 88.qt qml-TableView学习(一)_诺谦的博客-CSDN博客 所以本章便参考VUE-Element的Table外观组件实现一个可排序可操作的Table组件. 1.组件介绍 GIF如下所示: 排序支持数字和字符串排序。 …...
android 12.0SystemUI屏蔽某个app的通知
1.概述 在12.0的产品开发中,对于系统的通知部分,要求根据app包名来过滤掉一部分通知,就是在接收到系统通知时,根据包名判断是否需要接收通知的功能,首选要分析通知流程,然后实现功能 2.SystemUI屏蔽某个app的通知相关代码 frameworks\base\packages\SystemUI\src\com\…...
注意力机制(一)SE模块(Squeeze-and-Excitation Networks)论文总结和代码实现
Squeeze-and-Excitation Networks(压缩和激励网络) 论文地址:Squeeze-and-Excitation Networks 论文中文版:Squeeze-and-Excitation Networks_中文版 代码地址:GitHub - hujie-frank/SENet: Squeeze-and-Excitation Ne…...
2026权威评测:TOP5毕业论文AIGC降重方案对比与首选建议
全景速览:2026盲审季TOP5降重工具核心对比表 排名工具名称降重与去痕效能核心适用场景致命短板 / 核心优势1Scholingo靠岸妙写★★★★★国内本科/硕博盲审、核心期刊投稿优势:DOM级自定义大纲独家AIGC物理去痕2Paperpal★★★★☆SCI/海外顶刊纯英润色…...
【含文档+PPT+源码】基于SSM框架的农产品销售平台的设计与实现
项目介绍本课程演示的是一款 基于SSM框架的农产品销售平台的设计与实现,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。1.包含:项目源码、项目文档、数据库脚本、软件工具等所有资料2.带你从零开始部署运行本套系统3.该项…...
细致配置Doctrine,专注于指定前缀表的迁移
在使用Symfony和Doctrine进行项目开发时,如何优雅地处理数据库迁移是一个常见的问题。本文将详细探讨如何配置Doctrine,使其在生成迁移文件时仅关注特定前缀的表(如pp_前缀的表),从而避免迁移文件中包含不必要的表。 背景介绍 假设你有一个Symfony项目,该项目中数据库已…...
CRT库链接冲突详解:为什么你的Visual Studio项目会警告LNK4098(含/NODEFAULTLIB使用指南)
CRT库链接冲突深度解析:从原理到实战解决LNK4098警告 当你用Visual Studio编译C项目时,突然蹦出"warning LNK4098: 默认库msvcrtd.lib与其他库的使用冲突"的提示,这就像开车时仪表盘突然亮起的警告灯——它不会立即让引擎熄火&…...
Ollama实测:Yi-Coder-1.5B代码生成速度有多快?3秒搞定日常函数
Ollama实测:Yi-Coder-1.5B代码生成速度有多快?3秒搞定日常函数 1. 测试背景与目标 作为一名开发者,每天都要面对各种编码任务。从简单的工具函数到复杂的算法实现,代码生成速度直接影响着开发效率。Yi-Coder-1.5B作为一款开源的…...
从零构建uWSGI-Nginx-Flask-Docker镜像的5个核心步骤
从零构建uWSGI-Nginx-Flask-Docker镜像的5个核心步骤 【免费下载链接】uwsgi-nginx-flask-docker Docker image with uWSGI and Nginx for Flask applications in Python running in a single container. Optionally with Alpine Linux. 项目地址: https://gitcode.com/gh_mi…...
GLM-4v-9b效果展示:直播带货截图→话术分析+转化点提炼
GLM-4v-9b效果展示:直播带货截图→话术分析转化点提炼 1. 模型能力概览 GLM-4v-9b是智谱AI在2024年开源的多模态视觉-语言模型,拥有90亿参数。这个模型最大的特点是能够同时理解图片和文字,支持中英文多轮对话,在11201120高分辨…...
tomcat和国产web中间件区别和联系
国产中间件 宝蓝德 https://www.bessystem.com/product/e717be5b091e4e14a7339aa4be49ca80/info?p101东方通 https://www.tongtech.com/sy.html非国产tomcat tomcat的项目发布方式 将项目复制到tomcat/webapps中启动Tomcat服务器,双击 startup.bat访问项目 IDEA 中…...
cv_resnet101_face-detection_cvpr22papermogface保姆级教程:GPU显存占用监控与自动释放策略
cv_resnet101_face-detection_cvpr22papermogface保姆级教程:GPU显存占用监控与自动释放策略 1. 引言 如果你正在使用基于ResNet101的MogFace人脸检测模型,可能会遇到一个常见问题:GPU显存占用越来越高,最终导致程序崩溃。尤其是…...
新手零障碍入门:在免激活的快马平台完成你的第一个Python小游戏
作为一个刚接触编程的新手,我最近在InsCode(快马)平台上完成了人生第一个Python小游戏——猜数字。整个过程比想象中简单得多,特别适合像我这样零基础的小白入门。下面分享我的学习笔记,希望能帮到同样想尝试编程的朋友。 为什么选择猜数字游…...
