技术标签: 算法 c++ 链表 leetcode LCR(剑指offer) 数据结构
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表,你可以将左右孩子指针作为双向循环链表的前驱和后继指针,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
特别地,我们希望可以 就地 完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
示例 1:
输入:root = [4,2,5,1,3] 输出:[1,2,3,4,5] 解释:下图显示了转化后的二叉搜索树,实线表示后继关系,虚线表示前驱关系。
示例 2:
输入:root = [2,1,3]
输出:[1,2,3]
示例 3:
输入:root = []
输出:[]
解释:输入是空树,所以输出也是空链表。
示例 4:
输入:root = [1]
输出:[1]
提示:
-1000 <= Node.val <= 1000
Node.left.val < Node.val < Node.right.val
Node.val
的所有值都是独一无二的0 <= Number of Nodes <= 2000
思路:
1、二叉排序树的中序遍历结果即为有序列表。
2、分别定义一个空的前驱结点pre和一个空的需要返回的头结点head。
3、中序遍历至最左结点处,利用刚开始head为空的条件让head等于最小结点。
4、只有刚开始前驱结点pre为空,后面的遍历pre都不为空。除了刚开始,我们让pre右子树(后继)等于root,root的左子树(前驱)等于pre,即完成有序双向链表的建立。
5、pre=root,继续完成中序遍历,该遍历当前结点的右子树了。
6、最后pre指向最大结点处,我们让pre后继指向head,head前驱指向pre,返回head,完成!
代码实现:
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == NULL)
return NULL;
mid(root); //二叉搜索树中序遍历
head->left = pre;
pre->right = head;
return head;
}
void mid(Node* root)
{
if(root == NULL) //递归结束条件
return;
mid(root->left);
if(!head) //只有在head为空,此时遍历到最小结点处,我们让head等于最小结点
head = root;
if(pre) //刚开始pre为空,我们需要此条件来跳过第一次的后继链表构建
pre->right = root;
root->left = pre;
pre = root;
mid(root->right);
}
private:
Node* head = NULL;
Node* pre = NULL;
};
文章浏览阅读451次。dev/mem: 物理内存的全镜像。可以用来访问物理内存。/dev/kmem: kernel看到的虚拟内存的全镜像。可以用来访问kernel的内容。调试嵌入式Linux内核时,可能需要查看某个内核变量的值。/dev/kmem正好提供了访问内核虚拟内存的途径。现在的内核大都默认禁用了/dev/kmem,打开的方法是在 make menuconfig中选中 device drivers --> ..._dev/mem 源码实现
文章浏览阅读7.1k次,点赞2次,收藏19次。vxe-table,一个小众但功能齐全并支持excel操作的vue表格组件_vxe-table
文章浏览阅读62次。参考:http://www.ruanyifeng.com/blog/2016/01/babel.htmlBabelBabel是一个广泛使用的转码器,可以将ES6代码转为ES5代码,从而在现有环境执行// 转码前input.map(item => item + 1);// 转码后input.map(function (item) { return item..._让开发环境支持bable
文章浏览阅读2.8k次,点赞6次,收藏29次。摘要:FPGA视频处理FIFO的典型应用,视频输入FIFO的作用,视频输出FIFO的作用,视频数据跨时钟域FIFO,视频缩放FIFO的作用_fpga 频分复用 视频
文章浏览阅读575次。【代码】R语言:设置工作路径为当前文件存储路径。_r语言设置工作目录到目标文件夹
文章浏览阅读452次。格式:background: linear-gradient(direction, color-stop1, color-stop2, ...);<linear-gradient> = linear-gradient([ [ <angle> | to <side-or-corner>] ,]? &l..._background线性渐变
文章浏览阅读1k次,点赞26次,收藏8次。第十三届蓝桥杯青少年组python编程省赛真题一、题目要求(注:input()输入函数的括号中不允许添加任何信息)1、编程实现给定一个正整数N,输出正整数N中各数位最大的那个数字。例如:N=132,则输出3。2、输入输出输入描述:只有一行,输入一个正整数N输出描述:只有一行,输出正整数N中各数位最大的那个数字输入样例:
文章浏览阅读2.2k次。一个网络协议主要由以下三个要素组成:1.语法数据与控制信息的结构或格式,包括数据的组织方式、编码方式、信号电平的表示方式等。2.语义即需要发出何种控制信息,完成何种动作,以及做出何种应答,以实现数据交换的协调和差错处理。3.时序即事件实现顺序的详细说明,以实现速率匹配和排序。不完整理解:语法表示长什么样,语义表示能干什么,时序表示排序。转载于:https://blog.51cto.com/98..._网络协议三要素csdn
文章浏览阅读153次。主要的思想,将所有的系统都可以看作两部分,真正的数据log系统和各种各样的query engine所有的一致性由log系统来保证,其他各种query engine不需要考虑一致性,安全性,只需要不停的从log系统来同步数据,如果数据丢失或crash可以从log系统replay来恢复可以看出kafka系统在linkedin中的重要地位,不光是d..._the log: what every software engineer should know about real-time data's uni
文章浏览阅读746次。伟大是熬出来的 目录 前言 引言 时间熬成伟大:领导者要像狼一样坚忍 第一章 内圣外王——领导者的心态修炼 1. 天纵英才的自信心 2. 上天揽月的企图心 3. 誓不回头的决心 4. 宠辱不惊的平常心 5. 换位思考的同理心 6. 激情四射的热心 第二章 日清日高——领导者的高效能修炼 7. 积极主动,想到做到 8. 合理掌控自己的时间和生命 9. 制定目标,马..._当狼拖着受伤的右腿逃生时,右腿会成为前进的阻碍,它会毫不犹豫撕咬断自己的腿, 以
文章浏览阅读285次。在当今的大数据时代,人们对高速度和高带宽的需求越来越大,迫切希望有一种新型产品来作为高性能计算和数据中心的主要传输媒质,所以有源光缆(AOC)在这种环境下诞生了。有源光缆究竟是什么呢?应用在哪些领域,有什么优势呢?易天将为您解答!有源光缆(Active Optical Cables,简称AOC)是两端装有光收发器件的光纤线缆,主要构成部件分为光路和电路两部分。作为一种高性能计..._aoc 光缆
文章浏览阅读2.2k次。在“桌面”上按快捷键“Ctrl+R”,调出“运行”窗口。接着,在“打开”后的输入框中输入“Gpedit.msc”。并按“确定”按钮。如下图 找到“用户配置”下的“Windows设置”下的“Internet Explorer 维护”的“连接”,双击选择“自动浏览器配置”。如下图 选择“自动启动配置”,并在下面的“自动代理URL”中填写相应的PAC文件地址。如下..._設置proxy腳本