leetcode_117 填充每个节点的下一个右侧节点指针 II
文章目录
- 1. 题意
- 2. 题解
- 2.1 BFS
- 2.2 BFS+空间优化
- 2.3 DFS序+层次记录
- 3. Ref
1. 题意
在一颗树的同层之间用指针把他们链接起来。
填充每个节点的下一个右侧节点指针 II
2. 题解
2.1 BFS
用一个变量记录下同层最右侧的节点,当遍历到时更新下一层的最右侧节点即可。
class Solution {
public:Node* connect(Node* root) {Node *righMost = root;queue<Node *> q;if (root)q.push(root);while (!q.empty()) {Node *cur = q.front();q.pop();if ( cur -> left) q.push(cur->left);if ( cur->right )q.push(cur->right);if (cur == righMost) {righMost = q.back();}else {cur->next = q.front();}}return root;}
};
2.2 BFS+空间优化
在将下一层的节点放入队列时,其实就可以将他们链接起来了。从而省去了队列的空间,此时保存下每一层的最开始的节点就可以了。
class Solution {
public:void handle(Node *&pre, Node *&nextStart,Node *rt) {if (nullptr == rt) return ;if (!pre) {nextStart = rt;}else {pre->next = rt;}pre = rt;}Node* connect(Node* root) {Node *righMost = root;Node *start = root;Node *nextStart = nullptr;Node *pre = nullptr;for ( ;start; start = nextStart) {nextStart = nullptr;pre = nullptr;for ( ;start;start = start->next) {handle(pre, nextStart, start->left);handle(pre, nextStart, start->right);}}return root;}
};
2.3 DFS序+层次记录
利用先序遍历的永远是从左到又这一特点,用一个pre[depth]数组来记录当前DFS遍历到的该层的左侧节点。当再次遍历到该层时,链接pre[depth]节点到当前节点,并更新。
class Solution {
public:void handle(Node *&pre, Node *&nextStart,Node *rt) {if (nullptr == rt) return ;if (!pre) {nextStart = rt;}else {pre->next = rt;}pre = rt;}void dfs(std::vector<Node*> &pre, Node *root, int depth) {if (nullptr == root)return;int sz = pre.size();if (sz == depth) {pre.push_back(root);}else {pre[depth]->next = root;pre[depth] = root;}dfs(pre, root->left, depth + 1);dfs(pre, root->right, depth + 1);}Node* connect(Node* root) {vector<Node *> pre;dfs(pre, root, 0);return root;}
};
3. Ref
03xf题解
相关文章:
leetcode_117 填充每个节点的下一个右侧节点指针 II
文章目录 1. 题意2. 题解2.1 BFS2.2 BFS空间优化2.3 DFS序层次记录 3. Ref 1. 题意 在一颗树的同层之间用指针把他们链接起来。 填充每个节点的下一个右侧节点指针 II 2. 题解 2.1 BFS 用一个变量记录下同层最右侧的节点,当遍历到时更新下一层的最右侧节点即可…...
亲测 IDEA Pycharm 全家桶 自动重置免费30天
理论上是通用的 插件市场安装 添加第三方插件仓库地址 在Settings/Preferences... -> Plugins 内手动添加第三方插件仓库地址:https://plugins.zhile.io 搜索:IDE Eval Reset插件进行安装。如果搜索不到请注意是否做好了上一步?网络是否…...
Marp: 将 Markdown 变为 PPT 式样的 VScode 插件
样例代码: --- marp: true size: 16:9 theme: default header: footer: --- <!-- _footer: Jia ming<br>Gansu University of Political Science and Law --> <!-- _backgroundColor: lightskyblue --> ## <!-- fit --> 笔记检验概述>…...
根据正则表达式截取字串符,这个办法打败99%程序员
作为一名程序员,常常会在以下情况下使用函数功能根据正则表达式截取字符串: 1.字符串处理:当需要使用正则表达式匹配和提取字符串中的特定模式时,可以使用该函数。例如,从一段文本中提取电子邮件地址、电话号码或网站…...
冬天女儿的羽绒服就选它了,哈哈很喜欢
长款设计感满满的羽绒服 真的一下子就戳中了我的心巴 90白鸭绒+杜邦三防工艺+精细压线 厚实保暖不臃肿,粉色撞色甜美又可爱...
Vim插件配置
工欲善其事,必先利其器,倒腾一下vim的配置,做个记录。 ".vimrc里的内容:""for base configure set t_Co256 if ! has("gui_running")set t_Co256 endifif &diffhighlight DiffAdd ctermbold cte…...
函数参数的最佳传递方式与现代C++的规则
函数参数的最佳传递方式与现代C的规则 在C中,如何最佳地传递函数参数以及如何处理类的特殊成员函数,一直是优化性能和代码质量的重要话题。下面我将详细解释这些概念。 使用移动语义实现 Swap 函数 移动语义(Move Semantics)能…...
Asterisk Ubuntu 安装
更新环境 sudo apt update sudo apt install wget build-essential git autoconf subversion pkg-config libtool sudo contrib/scripts/get_mp3_source.sh A addons/mp3 A addons/mp3/common.c A addons/mp3/huffman.h A addons/mp3/tabinit.c A addons/mp3/Ma…...
rwkv模型lora微调之accelerate和deepspeed训练加速
目录 一、rwkv模型简介 二、lora原理简介 三、rwkv-lora微调 1、数据整理 2、环境搭建 a、Dockerfile编写 b、制造镜像 c、容器启动 3、训练代码修改 四、模型推理 1、模型推理 2、lora权重合并 3、推理web服务 五、总结 由于业务采用的ChatGLM模型推理成本太大了…...
分享一下在微信小程序里怎么做一个投票链接
在当今信息化社会,投票已成为各行各业收集意见、汇聚智慧的重要手段。传统的投票方式往往需要投入大量人力物力,而如今,借助微信小程序,我们可以在几分钟内创建一个高效、便捷的投票平台。本文将详细介绍如何在微信小程序中添加投…...
v-model语法糖
v-model原理 v-model实现双向绑定的语法糖,常用于表单与组件之间的数据双向绑定v-model本质上是 value属性和input事件的一层包装 v-model的作用:提供数据的双向绑定数据发生了改变,页面会自动变 v-bind:value页面输入改变 , 数据…...
纷享销客荣获最佳制造业数字营销服务商奖
2023年10月26日,第二届中国制造业数智化发展大会在上海盛大召开。本次大会汇聚了制造行业的顶尖企业和专家,共同探讨如何通过数字化转型赋能企业自身成长,实现信息化向数字化的升级转型。 在本次盛会上,纷享销客以其卓越的基本面、…...
蓝桥杯每日一题2023.11.3
题目描述 承压计算 - 蓝桥云课 (lanqiao.cn) 题目分析 将重量存入a中,每一层从上到下进行计算,用d进行计算列的重量,当前d的重量应为正上数组和右上数组的个半和并加上自身的重量 计算到30层记录最大最小值,进行比例运算即可 …...
中国电子云-隐私计算-云原生安全可信计算,物理-硬件-系统-云产品-云平台,数据安全防护
目录 联邦学习的架构思想 中国电子云-隐私计算-云原生安全...
PHP服务器端电商API原理及示例讲解(电商接口开发/接入)
下面小编就为大家分享一篇PHP服务器端API原理及示例讲解(接口开发),具有很好的参考价值,希望对大家有所帮助 相信大家都做过PHP请求电商API接口获取数据,比如淘宝平台商品API接口,订单接口,京东接口,1688接…...
Spring Cloud应用- Eureka原理、搭建
初期对Spring Cloud的学习以应用搭建为主,所以内容不会太枯燥。 一直以来,自以为Spring全家桶的学习中,Spring framework是基础中的基础,部分内容也还是必须要读源码去理解底层原理,SpringMVC、SpringBoot,…...
Servlet 设置启动时机(web.xml方式和@WebServlet方式)
1、通过web.xml方式 5)Servlet的启动时机 - 默认情况下,servlet是不会随着容器的启动而被实例化的,只有当第一次给我发请求时才会被实例化那么,这种情况对于第一次请求是不公平的因此,为了提高用户体验度,提高服务器的…...
一个使用uniapp+vue3+ts+pinia+uview-plus开发小程序的基础模板
uniappuviewPlusvue3tspiniavite 开发基础模板 使用 uniapp vue3 ts pinia vite 开发基础模板,拿来即可使用,不要删除 yarn.lock 文件,否则会启动报错,这个可能和 pinia 的版本有关,所以不要随意修改。 拉取代码…...
Kali安装docker
第一步:kali添加Docker官方的GPG密钥 curl -fsSL https://download.docker.com/linux/debian/gpg | sudo apt-key add 第二步:进入root更新源: su rootecho ‘deb https://download.docker.com/linux/debian stretch stable’> /etc/ap…...
Maven第七章:Maven工程最佳实践
Maven第七章:Maven工程最佳实践 前言 本章重点,通过一个maven工程最佳实践案例,熟悉和掌握maven在项目中的应用基本思路,让你的技能值瞬间暴涨。 最佳实践 确定项目的坐标和依赖 在Maven中,项目的坐标定义了项目的唯一标识符,包括groupId、artifactId和version。因此,在…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
