【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表
题目链接
剑指 Offer 36. 二叉搜索树与双向链表
标签
后序遍历、二叉搜索树
步骤
- 二叉搜索树中的任一节点的直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点。因此,可以通过这个关系来操作原来的二叉树。
- 为了不影响深度较大的节点的判断,使用后序遍历。
Step1. 后序遍历,寻找 root
的最左侧和最右侧节点,分别设为 head
, tail
。其中,head
是整棵树最左侧的节点,相当于中序遍历中最先输出的节点。
void postOrder(Node* root) {if (root == nullptr) {return;}postOrder(root->left);if (!findHead && root->left == nullptr) { // 设置头结点head = root;findHead = true;}postOrder(root->right);// 找左子树的最右侧节点: 直接前驱Node *rightest = findRightest(root->left);if (rightest != nullptr) {root->left = rightest;rightest->right = root;}// 找右子树的最左侧节点:直接后继Node *leftest = findLeftest(root->right);if (leftest == nullptr) {tail = root;} else {root->right = leftest;leftest->left = root;}
}
Step2. 补充寻找指定节点左子树最右侧、右子树最右侧的节点的代码。
/* Node *leftest = findLeftest(root->right),*rightest = findRightest(root->left);*/
Node* findRightest(Node* root) { // 找以root为根的二叉树中,最右侧的节点if (root == nullptr) {return nullptr;}while (root->right != nullptr) {root = root->right;}return root;
}
Node* findLeftest(Node* root) {if (root == nullptr) {return nullptr;}while (root->left != nullptr) {root = root->left;}return root;
}
Step3. 构建 head
和 tail
之间的联系。
head->left = tail;
tail->right = head;
实现代码(C++)
class Solution {
public:Node *head, *tail;bool findHead = false;Node* findRightest(Node* root) {if (root == nullptr) {return nullptr;}while (root->right != nullptr) {root = root->right;}return root;}Node* findLeftest(Node* root) {if (root == nullptr) {return nullptr;}while (root->left != nullptr) {root = root->left;}return root;}void postOrder(Node* root) {if (root == nullptr) {return;}postOrder(root->left);if (!findHead && root->left == nullptr) { // 设置头结点head = root;findHead = true;}postOrder(root->right);// 找左子树的最右侧节点: 直接前驱Node *rightest = findRightest(root->left);if (rightest != nullptr) {root->left = rightest;rightest->right = root;}// 找右子树的最左侧节点:直接后继Node *leftest = findLeftest(root->right);if (leftest == nullptr) {tail = root;} else {root->right = leftest;leftest->left = root;}}Node* treeToDoublyList(Node* root) {if (root == nullptr) {return nullptr;}postOrder(root);head->left = tail;tail->right = head;return head;}
};
相关文章:
【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表
题目链接 剑指 Offer 36. 二叉搜索树与双向链表 标签 后序遍历、二叉搜索树 步骤 二叉搜索树中的任一节点的直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点。因此,可以通过这个关系来操作原来的二叉树。为了不影响深度较大的节点的…...

Linux —— 文件系统
目录 一,背景 二,文件系统 一,磁盘简介 磁盘分为SSD、机械磁盘;机械磁盘,即磁盘高速转动,磁头移动到读写扇区所在磁道,让磁头在目标扇区上划过,即可完成对扇区的读写操作ÿ…...
自然策略优化的解释 Natural Policy Optimization
Natural Policy Optimization(自然策略优化)是一种用于优化策略梯度算法的方法。它是基于概率策略的强化学习算法,旨在通过迭代地更新策略参数来最大化累积回报。 传统的策略梯度算法通常使用梯度上升法来更新策略参数,但这种方法…...

docker基本使用方法
docker使用 1. Docker 介绍 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。Docker 使您能够将应用程序与基础架构分开,从而可以快速交付软件。通过利用 …...

机器学习(十八):Bagging和随机森林
全文共10000余字,预计阅读时间约30~40分钟 | 满满干货(附数据及代码),建议收藏! 本文目标:理解什么是集成学习,明确Bagging算法的过程,熟悉随机森林算法的原理及其在Sklearn中的各参数定义和使用方法 代码…...

使用蓝牙外设却不小心把台式机电脑蓝牙关了
起因 今天犯了一个贼SB的错误,起因是蓝牙键盘突然就不能输入了(虽然是连接状态,但是按什么键都没有反应) 原来我的解决方法就是重启一下电脑,但是那会电脑开了贼多的软件。我就想重启也太麻烦了,既然重启…...
美国Linux服务器安装Grafana和配置zabbix数据源的教程
美国Linux服务器的Grafana工具是跨平台、开源、时序和可视化面板Dashboard监控平台工具,是在日常管理中帮忙提高效率的实用工具,可以通过将采集的美国Linux服务器系统数据查询后,进行可视化的展示及通知,本文小编就来介绍下美国Li…...
[ROS安装问题] rosdep update 失败报错
【关于ROS安装】 由于日益复杂的国际形势,按照wiki官网的ROS安装流程变得相当困难,这里我推荐使用鱼香ROS大佬写的脚本一键傻瓜式安装: wget http://fishros.com/install -O fishros && . fishros 【关于rosdep失败】 这已经是一…...

Vue2到3 Day5 全套学习内容,众多案例上手(内付源码)
简介: Vue2到3 Day1-3 全套学习内容,众多案例上手(内付源码)_星辰大海1412的博客-CSDN博客本文是一篇入门级的Vue.js介绍文章,旨在帮助读者了解Vue.js框架的基本概念和核心功能。Vue.js是一款流行的JavaScript前端框架…...

STM32 CubeMX (uart_IAP串口)简单示例
STM32 CubeMX STM32 CubeMX (串口IAP) STM32 CubeMXIAP有什么用?整体思路 一、STM32 CubeMX 设置时钟树UART使能UART初始化设置 二、代码部分文件移植
Kafka:安装和配置
producer:发布消息的对象,称为消息产生者 (Kafka topic producer) topic:Kafka将消息分门别类,每一个消息称为一个主题(topic) consumer:订阅消息并处理发布消息的对象…...
786. 第k个数
文章目录 QuestionIdeasCode Question 给定一个长度为 n 的整数数列,以及一个整数 k ,请用快速选择算法求出数列从小到大排序后的第 k 个数。 输入格式 第一行包含两个整数 n 和 k 。 第二行包含 n 个整数(所有整数均在 1∼109 范围内&…...

用友-NC-Cloud远程代码执行漏洞[2023-HW]
用友-NC-Cloud远程代码执行漏洞[2023-HW] 一、漏洞介绍二、资产搜索三、漏洞复现PoC小龙POC检测脚本: 四、修复建议 免责声明:请勿利用文章内的相关技术从事非法测试,由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#…...

Transformer(二)(VIT,TNT)(基于视觉CV)
目录 1.视觉中的Attention 2.VIT框架(图像分类,不需要decoder) 2.1整体框架 2.2.CNN和Transformer遇到的问题 2.3.1CNN 2.3.2Transformer 2.3.3二者对比 2.4.公式理解 3TNT 参考文献 1.视觉中的Attention 对于人类而言看到一幅图可以立…...

Scratch 详解 之 线性→代数之——求两线段交点坐标
可能有人要问:求交点坐标有什么用呢?而且为啥要用线代来求?直线方程不行吗??? 这个问题,我只能说,直线方程计算的次数过多了,而且动不动就要考虑线的方向,90的…...

Python-组合数据类型
今天要介绍的是Python的组合数据类型 整理不易,希望得到大家的支持,欢迎各位读者评论点赞收藏 感谢! 目录 知识点知识导图1、组合数据类型的基本概念1.1 组合数据类型1.2 集合类型概述1.3 序列类型概述1.4 映射类型概述 2、列表类型2.1 列表的…...
vue3+vue-simple-uploader实现大文件上传
vue-simple-uploader本身是基于vue2实现,如果要使用vue3会报错。如何在vue3中使用,可参考我的另一篇文章:解决vue3中不能使用vue-simple-uploader__Jyann_的博客-CSDN博客 一.实现思路 使用vue-simple-uploader组件的uploader组件,设置自动上传为false,即可开启手动上传。…...

自适应变异麻雀搜索算法及其Matlab实现
麻雀搜索算法( sparrow search algorithm,SSA) 是2020 年新提出的一种元启发式算法[1],它是受麻雀种群的觅食和反捕食行为启发,将搜索群体分为发现者、加入者和侦察者 3 部分,其相互分工寻找最优值,通过 19 个标准测试…...

ETL技术入门之ETLCloud初认识
首先ETL是什么? ETL代表“Extract, Transform, Load”,是一种用于数据集成和转换的过程。它在数据管理和分析中扮演着重要的角色。下面我们将分解每个步骤: Extract(抽取): 这一步骤涉及从多个不同的数据源…...

uniapp项目如何运行在微信小程序模拟器上
在HbuilderX中的小程序写完后自己一定要保存,否则会出不来效果 那么怎么让uniapp项目运行在微信小程序开发工具中呢 1 在hbuilderx中点击运行到小程序模拟器 2 然后在项目目录中会生成一个文件夹 在微信小程序开发软件中的工具>安全设置>打开端口 或者在微…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...

海云安高敏捷信创白盒SCAP入选《中国网络安全细分领域产品名录》
近日,嘶吼安全产业研究院发布《中国网络安全细分领域产品名录》,海云安高敏捷信创白盒(SCAP)成功入选软件供应链安全领域产品名录。 在数字化转型加速的今天,网络安全已成为企业生存与发展的核心基石,为了解…...

leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
JavaScript 标签加载
目录 JavaScript 标签加载script 标签的 async 和 defer 属性,分别代表什么,有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...
Docker、Wsl 打包迁移环境
电脑需要开启wsl2 可以使用wsl -v 查看当前的版本 wsl -v WSL 版本: 2.2.4.0 内核版本: 5.15.153.1-2 WSLg 版本: 1.0.61 MSRDC 版本: 1.2.5326 Direct3D 版本: 1.611.1-81528511 DXCore 版本: 10.0.2609…...