当前位置: 首页 > 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…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

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

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

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...