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

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 用一个变量记录下同层最右侧的节点&#xff0c;当遍历到时更新下一层的最右侧节点即可…...

亲测 IDEA Pycharm 全家桶 自动重置免费30天

理论上是通用的 插件市场安装 添加第三方插件仓库地址 在Settings/Preferences... -> Plugins 内手动添加第三方插件仓库地址&#xff1a;https://plugins.zhile.io 搜索&#xff1a;IDE Eval Reset插件进行安装。如果搜索不到请注意是否做好了上一步&#xff1f;网络是否…...

Marp: 将 Markdown 变为 PPT 式样的 VScode 插件

样例代码&#xff1a; --- marp: true size: 16:9 theme: default header: footer: --- <!-- _footer: Jia ming<br>Gansu University of Political Science and Law --> <!-- _backgroundColor: lightskyblue --> ## <!-- fit --> 笔记检验概述>…...

根据正则表达式截取字串符,这个办法打败99%程序员

作为一名程序员&#xff0c;常常会在以下情况下使用函数功能根据正则表达式截取字符串&#xff1a; 1.字符串处理&#xff1a;当需要使用正则表达式匹配和提取字符串中的特定模式时&#xff0c;可以使用该函数。例如&#xff0c;从一段文本中提取电子邮件地址、电话号码或网站…...

冬天女儿的羽绒服就选它了,哈哈很喜欢

长款设计感满满的羽绒服 真的一下子就戳中了我的心巴 90白鸭绒&#xff0b;杜邦三防工艺&#xff0b;精细压线 厚实保暖不臃肿&#xff0c;粉色撞色甜美又可爱...

Vim插件配置

工欲善其事&#xff0c;必先利其器&#xff0c;倒腾一下vim的配置&#xff0c;做个记录。 ".vimrc里的内容&#xff1a;""for base configure set t_Co256 if ! has("gui_running")set t_Co256 endifif &diffhighlight DiffAdd ctermbold cte…...

函数参数的最佳传递方式与现代C++的规则

函数参数的最佳传递方式与现代C的规则 在C中&#xff0c;如何最佳地传递函数参数以及如何处理类的特殊成员函数&#xff0c;一直是优化性能和代码质量的重要话题。下面我将详细解释这些概念。 使用移动语义实现 Swap 函数 移动语义&#xff08;Move Semantics&#xff09;能…...

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模型推理成本太大了…...

分享一下在微信小程序里怎么做一个投票链接

在当今信息化社会&#xff0c;投票已成为各行各业收集意见、汇聚智慧的重要手段。传统的投票方式往往需要投入大量人力物力&#xff0c;而如今&#xff0c;借助微信小程序&#xff0c;我们可以在几分钟内创建一个高效、便捷的投票平台。本文将详细介绍如何在微信小程序中添加投…...

v-model语法糖

v-model原理 v-model实现双向绑定的语法糖&#xff0c;常用于表单与组件之间的数据双向绑定v-model本质上是 value属性和input事件的一层包装 v-model的作用&#xff1a;提供数据的双向绑定数据发生了改变&#xff0c;页面会自动变 v-bind:value页面输入改变 &#xff0c; 数据…...

纷享销客荣获最佳制造业数字营销服务商奖

2023年10月26日&#xff0c;第二届中国制造业数智化发展大会在上海盛大召开。本次大会汇聚了制造行业的顶尖企业和专家&#xff0c;共同探讨如何通过数字化转型赋能企业自身成长&#xff0c;实现信息化向数字化的升级转型。 在本次盛会上&#xff0c;纷享销客以其卓越的基本面、…...

蓝桥杯每日一题2023.11.3

题目描述 承压计算 - 蓝桥云课 (lanqiao.cn) 题目分析 将重量存入a中&#xff0c;每一层从上到下进行计算&#xff0c;用d进行计算列的重量&#xff0c;当前d的重量应为正上数组和右上数组的个半和并加上自身的重量 计算到30层记录最大最小值&#xff0c;进行比例运算即可 …...

中国电子云-隐私计算-云原生安全可信计算,物理-硬件-系统-云产品-云平台,数据安全防护

目录 联邦学习的架构思想 中国电子云-隐私计算-云原生安全...

PHP服务器端电商API原理及示例讲解(电商接口开发/接入)

下面小编就为大家分享一篇PHP服务器端API原理及示例讲解(接口开发)&#xff0c;具有很好的参考价值&#xff0c;希望对大家有所帮助 相信大家都做过PHP请求电商API接口获取数据&#xff0c;比如淘宝平台商品API接口&#xff0c;订单接口&#xff0c;京东接口&#xff0c;1688接…...

Spring Cloud应用- Eureka原理、搭建

初期对Spring Cloud的学习以应用搭建为主&#xff0c;所以内容不会太枯燥。 一直以来&#xff0c;自以为Spring全家桶的学习中&#xff0c;Spring framework是基础中的基础&#xff0c;部分内容也还是必须要读源码去理解底层原理&#xff0c;SpringMVC、SpringBoot&#xff0c…...

Servlet 设置启动时机(web.xml方式和@WebServlet方式)

1、通过web.xml方式 5)Servlet的启动时机 - 默认情况下&#xff0c;servlet是不会随着容器的启动而被实例化的&#xff0c;只有当第一次给我发请求时才会被实例化那么&#xff0c;这种情况对于第一次请求是不公平的因此&#xff0c;为了提高用户体验度&#xff0c;提高服务器的…...

一个使用uniapp+vue3+ts+pinia+uview-plus开发小程序的基础模板

uniappuviewPlusvue3tspiniavite 开发基础模板 使用 uniapp vue3 ts pinia vite 开发基础模板&#xff0c;拿来即可使用&#xff0c;不要删除 yarn.lock 文件&#xff0c;否则会启动报错&#xff0c;这个可能和 pinia 的版本有关&#xff0c;所以不要随意修改。 拉取代码…...

Kali安装docker

第一步&#xff1a;kali添加Docker官方的GPG密钥 curl -fsSL https://download.docker.com/linux/debian/gpg | sudo apt-key add 第二步&#xff1a;进入root更新源&#xff1a; su rootecho ‘deb https://download.docker.com/linux/debian stretch stable’> /etc/ap…...

Maven第七章:Maven工程最佳实践

Maven第七章:Maven工程最佳实践 前言 本章重点,通过一个maven工程最佳实践案例,熟悉和掌握maven在项目中的应用基本思路,让你的技能值瞬间暴涨。 最佳实践 确定项目的坐标和依赖 在Maven中,项目的坐标定义了项目的唯一标识符,包括groupId、artifactId和version。因此,在…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...