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

【题解】二叉搜索树与双向链表

二叉搜索树与双向链表

题目链接:二叉搜索树与双向链表

解题思路1:递归+中序遍历

首先题目最后要求的是一个的递增的双向链表,而二叉搜索树也是一类非常有特色的树,它的根节点大于所有左侧的节点,同时又小于所有右侧的节点,如果我们按照左中右去遍历这颗二叉树,恰巧得到的就是一个递增序列

题目同时要求不要创建新的节点,这样我们就需要在原有树上进行操作,树有左右节点指针,双向链表有前后两个指针,正好一一对应,我们修改指针指向,结合中序遍历,得到一颗递增的双向链表

代码如下:

	TreeNode* head = nullptr;TreeNode* pre = nullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;//递归的结束条件Convert(pRootOfTree->left);//递归到最左节点,是最小值if(pre == nullptr){//此时pRootOfTree是最左节点,是链表的head//初始化head和prehead = pRootOfTree;pre = pRootOfTree;}else{//pre是每一个pRootOfTree的前驱节点pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;}Convert(pRootOfTree->right);return head;}

解题思路2:非递归+栈

我们利用栈先进后出的特性,来模拟中序遍历出所有元素,先让所有左侧的元素进栈,再依次取出其父节点,再找该节点的右节点,将节点进行连接,连接方式和上一种思路一样

    TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree == nullptr) return nullptr;TreeNode* head = nullptr;TreeNode* pre = nullptr;stack<TreeNode*> s;while(pRootOfTree!=nullptr || !s.empty()){while(pRootOfTree!=nullptr){s.push(pRootOfTree);pRootOfTree = pRootOfTree->left;}pRootOfTree = s.top();s.pop();if(pre == nullptr){head = pRootOfTree;pre = pRootOfTree;}else{pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;}pRootOfTree = pRootOfTree->right;}return head;}

相关文章:

【题解】二叉搜索树与双向链表

二叉搜索树与双向链表 题目链接&#xff1a;二叉搜索树与双向链表 解题思路1&#xff1a;递归中序遍历 首先题目最后要求的是一个的递增的双向链表&#xff0c;而二叉搜索树也是一类非常有特色的树&#xff0c;它的根节点大于所有左侧的节点&#xff0c;同时又小于所有右侧的…...

【真实案例】解决后端接口调用偶尔超时问题

文章目录 背景分析代码分析二次日志分析排查Gateway服务解决解决办法1:添加重试机制解决办法2:优化网关内存分配解决办法3:调整OOM策略背景 项目从虚拟机迁移到k8s云原生平台(RainBond)后,发现偶尔会出现接口调用超时的问题。 统计了一下从上线到现在近一个月的调用失败…...

操作符详解(1)

1. 操作符分类&#xff1a; 算术操作符 移位操作符 位操作符 赋值操作符 单目操作符 关系操作符 逻辑操作符 条件操作符 逗号表达式 下标引用、函数调用和结构成员 2. 算术操作符 - * / % 1. 除了 % 操作符之外&#xff0c;其他的几个操作符可以作用于整数和浮点数。 2. 对…...

<指针进阶>指针数组和数组指针傻傻分不清?

✨Blog&#xff1a;&#x1f970;不会敲代码的小张:)&#x1f970; &#x1f251;推荐专栏&#xff1a;C语言&#x1f92a;、Cpp&#x1f636;‍&#x1f32b;️、数据结构初阶&#x1f480; &#x1f4bd;座右铭&#xff1a;“記住&#xff0c;每一天都是一個新的開始&#x1…...

无代码集成飞书连接更多应用

场景描述&#xff1a; 基于飞书开放平台能力&#xff0c;无代码集成飞书连接更多应用&#xff0c;打通数据孤岛。通过Aboter可轻松搭建业务自动化流程&#xff0c;实现多个应用之间的数据连接。 支持包括飞书事件监听和接口调用的能力&#xff1a; 事件监听&#xff1a; 用…...

三分钟解决AE缓存预览渲染错误、暂停、卡顿问题

一、清除RAM缓存&#xff08;内存&#xff09; 你应该做的第一件事是清除你的RAM。这将清除当前存储在内存中的所有临时缓存文件。要执行此操作&#xff0c;请导航到编辑>清除>所有内存。这将从头开始重置RAM缓存 二、清空磁盘缓存 您也可以尝试清空磁盘缓存。执行此操作…...

朴实无华的数据增强然后训练一下应用在电网异物检测领域,好像有自己的数据集就能发文了

RCNN-based foreign object detection for securing power transmission lines (RCNN4SPTL) Abstract 本文提出了一种新的深度学习网络——RCNN4SPTL (RCNN -based Foreign Object Detection for Securing Power Transmission lines)&#xff0c;该网络适用于检测输电线路上的…...

【使用教程】在Ubuntu下运行CANopen通信PMM伺服电机使用教程(NimServoSDK_V2.0.0)

本教程将指导您在Ubuntu操作系统下使用NimServoSDK_V2.0.0来运行CANopen通信的PMM系列一体化伺服电机。我们将介绍必要的步骤和命令&#xff0c;以确保您能够成功地配置和控制PMM系列一体化伺服电机。 NimServoSDK_V2.0.0是一款用于PMM一体化伺服电机的软件开发工具包。它提供了…...

vue3+ts+vite项目页面初始化loading加载效果

简介 一分钟实现 vue-pure-admin 同款项目加载时的 loading 效果 一、先看效果 1.1 静态效果 1.2 动态效果 二、上代码 核心代码在body里面&#xff0c;代码中已标明。找到你项目的 index.html &#xff0c;复制粘贴进去即可 <!DOCTYPE html> <html lang"en…...

ElasticSearch 数据聚合、自动补全(自定义分词器)、数据同步

文章目录 数据聚合一、聚合的种类二、DSL实现聚合1、Bucket&#xff08;桶&#xff09;聚合2、Metrics&#xff08;度量&#xff09;聚合 三、RestAPI实现聚合 自动补全一、拼音分词器二、自定义分词器三、自动补全查询四、实现搜索款自动补全&#xff08;例酒店信息&#xff0…...

神经网络基础-神经网络补充概念-18-多个样本的向量化

概念 多个样本的向量化通常涉及将一组样本数据组织成矩阵形式&#xff0c;其中每一行代表一个样本&#xff0c;每一列代表样本的特征。这种向量化可以使你更有效地处理和操作多个样本&#xff0c;特别是在机器学习和数据分析中。 代码实现 import numpy as np# 多个样本的数…...

*看门狗1

//while部分是我们在项目中具体需要写的代码&#xff0c;这部分的程序可以用独立看门狗来监控 //如果我们知道这部分代码的执行时间&#xff0c;比如是500ms&#xff0c;那么我们可以设置独立看门狗的 //溢出时间是600ms&#xff0c;比500ms多一点&#xff0c;如果要被监控的程…...

nginx防盗链

防盗链介绍 通过二次访问&#xff0c;请求头中带有referer&#xff0c;的方式不允许访问静态资源。 我们只希望用户通过反向代理服务器才可以拿到我们的静态资源&#xff0c;不希望别的服务器通过二次请求拿到我们的静态资源。 盗链是指在自己的页面上展示一些并不在自己服务…...

8月16日上课内容 第二章 部署LVS-DR群集

本章结构&#xff1a; 数据包流向分析: 数据包流向分析&#xff1a; &#xff08;1&#xff09;客户端发送请求到 Director Server&#xff08;负载均衡器&#xff09;&#xff0c;请求的数据报文&#xff08;源 IP 是 CIP,目标 IP 是 VIP&#xff09;到达内核空间。 &#xf…...

ViT模型架构和CNN区别

目录 Vision Transformer如何工作 ViT模型架构 ViT工作原理解析 步骤1&#xff1a;将图片转换成patches序列 步骤2&#xff1a;将patches铺平 步骤3&#xff1a;添加Position embedding 步骤4&#xff1a;添加class token 步骤5&#xff1a;输入Transformer Encoder 步…...

发布python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api,以及安卓接入案例代码

python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api&#xff0c;以及原生安卓接入案例代码案例 源码地址:keyxh/newsapi: python模仿2023年全国职业的移动应用开发赛项样式开发的开源的新闻api&#xff0c;以及安卓接入案例代码 (github.com) 目录 1.环境配…...

adb command

查看屏幕分辨率 adb shell wm size 查看dpi adb shell dumpsys window | grep ‘dpi’ WIFI调试&#xff1a; adb tcpip 5555adb connect 设备ip 注意&#xff0c;USB拔插会断掉&#xff0c;所以插上USB后再 adb connect 设备ip。【注意】华为手机自建热点的ip一般是192.1…...

在ARM服务器上一键安装Proxmox VE(以在Oracle Cloud VPS上为例)(甲骨文)

前言 如题&#xff0c;具体用到的说明文档如下 virt.spiritlhl.net 具体流程 首先是按照说明&#xff0c;先得看看自己的服务器符不符合安装 Proxmox VE的条件 https://virt.spiritlhl.net/guide/pve_precheck.html#%E5%90%84%E7%A7%8D%E8%A6%81%E6%B1%82 有提到硬件和软…...

KMP算法(JS)

KMP算法 什么时KMP算法 KMP算法是一种改进的字符串匹配算法 由D.E.Knuth&#xff0c;J.H.Morris和 V.R.Pratt提出的&#xff0c;因此人们称它为克努特—莫里斯—普拉特操作&#xff08;简称KMP算法&#xff09;。 KMP的主要思想是当出现字符串不匹配时&#xff0c;可以知道…...

恢复NuGet包_解决:System.BadImageFormatException:无法加载文件或程序集

C#工程 主要是开发了一个 web api接口&#xff0c;这个工程源码去年还可以的&#xff0c;今年换了一个电脑打开工程就报错。 错误提示如下&#xff1a; 在 Microsoft.CodeAnalysis.CSharp.CommandLine.Program.Main(String[] args) Test1 System.BadImageFormatEx…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...