将二叉查找树转换成双链表
将一个二叉查找树按照中序遍历转换成双向链表。
样例
给定一个二叉查找树:
返回 1<->2<->3<->4<->5。标签
链表
code
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
* Definition of Doubly-ListNode
* class DoublyListNode {
* public:
* int val;
* DoublyListNode *next, *prev;
* DoublyListNode(int val) {
* this->val = val;
this->prev = this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of tree
* @return: the head of doubly list node
*/
DoublyListNode* bstToDoublyList(TreeNode* root) {
// Write your code here
DoublyListNode* head=NULL;
vector<int> list;
if(root == NULL)
return head;
treeToList(root, list);
head = listToDlist(list);
return head;
}
void treeToList(TreeNode *TreeRoot, vector<int> &list) {
if(TreeRoot != NULL) {
treeToList(TreeRoot->left, list);
list.push_back(TreeRoot->val);
treeToList(TreeRoot->right, list);
}
}
DoublyListNode* listToDlist(vector<int> &list) {
DoublyListNode* head=NULL,* p=NULL,* q=NULL;
int size = list.size();
if(0 == size)
return head;
head = p = q = new DoublyListNode(list[0]);
for(int i=1; i<size; i++) {
p->next = new DoublyListNode(list[i]);
p->next->prev = q;
q = p->next;
p = p->next;
}
return head;
}
};
LintCode-378.将二叉查找树转换成双链表的更多相关文章
-
lintcode:将二叉查找树转换成双链表
题目 将一个二叉查找树按照中序遍历转换成双向链表 给定一个二叉查找树: 4 / \ 2 5 / \ 1 3 返回 1<->2<->3<->4<->5. ...
-
BST转换成有序链表
把二元查找树转变成排序的双向链表(树)题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. struct BSTreeNode{ int va ...
-
双链表算法原理【Java实现】(八)
前言 前面两节内容我们详细介绍了ArrayList,一是手写实现ArrayList数据结构,而是通过分析ArrayList源码看看内置实现,关于集合内容一如既往,本节课我们继续学习集合LinkedLi ...
-
【LeetCode-面试算法经典-Java实现】【109-Convert Sorted List to Binary Search Tree(排序链表转换成二叉排序树)】
[109-Convert Sorted List to Binary Search Tree(排序链表转换成二叉排序树)] [LeetCode-面试算法经典-Java实现][全部题目文件夹索引] 原题 ...
-
(转)为什么HashMap中链表长度超过8会转换成红黑树
原博地址:https://blog.csdn.net/xingfei_work/article/details/79637878 HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素 ...
-
JavaScript:将key和value不带双引号的JSON字符串转换成JSON对象的方法
遇到相关的问题,花了两天的时间来解决,深感来之不易,所以做如下的总结,希望遇到此问题的码农能更快的找到解决办法! var jsonArr= [{col:TO_CHAR(HZRQ,'YYYYMM'),t ...
-
C语言:将ss所指字符串中所有下标为奇数位上的字母转换成大写,若不是字母,则不转换。-删除指针p所指字符串中的所有空白字符(包括制表符,回车符,换行符)-在带头结点的单向链表中,查找数据域中值为ch的结点,找到后通过函数值返回该结点在链表中所处的顺序号,
//将ss所指字符串中所有下标为奇数位上的字母转换成大写,若不是字母,则不转换. #include <stdio.h> #include <string.h> void fun ...
-
【遍历二叉树】11把二叉树转换成前序遍历的链表【Flatten Binary Tree to Linked List】
本质上是二叉树的root->right->left遍历. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ...
-
C和指针 第十二章 使用结构和指针 双链表和语句提炼
双链表中每个节点包含指向当前和之后节点的指针,插入节点到双链表中需要考虑四种情况: 1.插入到链表头部 2.插入到链表尾部 3.插入到空链表中 4.插入到链表内部 #include <stdio ...
随机推荐
-
ansible非root用户批量修改root密码
前言: 由于线上服务器密码长久没有更新,现领导要求批量更换密码.线上的之前部署过salt,但由于各种因素没有正常使用. 使用自动化工具批量修改的计划搁浅了,后来领导给了个python多线程修改密码脚本 ...
-
html特殊字符的html,js,css写法汇总
⇠ 箭头类 符号 UNICODE 符号 UNICODE HTML JS CSS HTML JS CSS ⇠ ⇠ \u21E0 \21E0 ⇢ ⇢ \u21E2 \ ...
-
链表与Hash检索实测
测试环境: Win7 SP1.8G内存.3.4GHz 4核 测试代码: using System; using System.Collections.Generic; using System.Lin ...
-
j2ee开源项目——IT学习者博客(itxxzblog v1.0)
大家好,我是IT学习者-螃蟹,已经有近一周的时间没有更新文章了,作为回报,今天起将更新一个大件,也就是螃蟹还在进行中的IT学习者博客. IT学习者博客的初期设计已经完成,功能也已经完成了大半,具备了当 ...
-
nodejs后台集成富文本编辑器(ueditor)
1 下载ueditor nodejs版本 2 复制public目录下面的文件 到项目静态资源public文件夹下 3 在项目根目录创建ueditor文件夹 要复制进来的内容为 4 在根目录的 uedi ...
-
网络基础tcp/ip协议二
物理层解析: 物理层是TCP/IP模型的最低层,物理层为数据提供数据传输可靠通路. 物理层关心的介质: 信号 接口 传输介质 信号的分类:(信号是信息传递的媒介.) 模拟信号:连续变化的物理量 数字信 ...
-
纯CSS下拉菜单(希望对有需要的小伙伴有所帮助)
效果截图(颜色有点丑,请无视): <!DOCTYPE html> <html> <head> <meta charset="utf-8" ...
-
# RocEDU.课程设计2018 第三周进展 博客补交
RocEDU.课程设计2018 第三周进展 博客补交 本周计划完成的任务 (1).本周计划完成在平板电脑上实现程序的功能,跟第二周计划完成任务基本相似. 本周实际完成情况 (1).实际完成情况还差最后 ...
-
ArcGIS Server 服务器日志(待修改)
有时遇到服务相关错误,需要查看日志来排查,这里简单写下日志相关操作. 服务器日志:http://resources.arcgis.com/zh-cn/help/main/10.2/index.html ...
-
MySQL数据记录大小写敏感问题【转】
MySQL大小写敏感 字符串大小写敏感和Mysql的数据库的名字.表名字.字段名字.还有字段值有关. 1.和数据库名字.表名字.存储过程和触发器有关 为0时:表示区分大小写,使用CREATE TABL ...