LintCode-378.将二叉查找树转换成双链表

时间:2022-02-13 07:54:49

将二叉查找树转换成双链表

将一个二叉查找树按照中序遍历转换成双向链表。

样例

给定一个二叉查找树:

LintCode-378.将二叉查找树转换成双链表

返回 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.将二叉查找树转换成双链表的更多相关文章

  1. lintcode:将二叉查找树转换成双链表

    题目 将一个二叉查找树按照中序遍历转换成双向链表 给定一个二叉查找树: 4 / \ 2 5 / \ 1 3 返回 1<->2<->3<->4<->5. ...

  2. BST转换成有序链表

    把二元查找树转变成排序的双向链表(树)题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. struct BSTreeNode{ int va ...

  3. 双链表算法原理【Java实现】(八)

    前言 前面两节内容我们详细介绍了ArrayList,一是手写实现ArrayList数据结构,而是通过分析ArrayList源码看看内置实现,关于集合内容一如既往,本节课我们继续学习集合LinkedLi ...

  4. 【LeetCode-面试算法经典-Java实现】【109-Convert Sorted List to Binary Search Tree(排序链表转换成二叉排序树)】

    [109-Convert Sorted List to Binary Search Tree(排序链表转换成二叉排序树)] [LeetCode-面试算法经典-Java实现][全部题目文件夹索引] 原题 ...

  5. &lpar;转&rpar;为什么HashMap中链表长度超过8会转换成红黑树

    原博地址:https://blog.csdn.net/xingfei_work/article/details/79637878 HashMap在jdk1.8之后引入了红黑树的概念,表示若桶中链表元素 ...

  6. JavaScript&colon;将key和value不带双引号的JSON字符串转换成JSON对象的方法

    遇到相关的问题,花了两天的时间来解决,深感来之不易,所以做如下的总结,希望遇到此问题的码农能更快的找到解决办法! var jsonArr= [{col:TO_CHAR(HZRQ,'YYYYMM'),t ...

  7. C语言:将ss所指字符串中所有下标为奇数位上的字母转换成大写,若不是字母,则不转换。-删除指针p所指字符串中的所有空白字符(包括制表符,回车符,换行符)-在带头结点的单向链表中,查找数据域中值为ch的结点,找到后通过函数值返回该结点在链表中所处的顺序号,

    //将ss所指字符串中所有下标为奇数位上的字母转换成大写,若不是字母,则不转换. #include <stdio.h> #include <string.h> void fun ...

  8. 【遍历二叉树】11把二叉树转换成前序遍历的链表【Flatten Binary Tree to Linked List】

    本质上是二叉树的root->right->left遍历. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ...

  9. C和指针 第十二章 使用结构和指针 双链表和语句提炼

    双链表中每个节点包含指向当前和之后节点的指针,插入节点到双链表中需要考虑四种情况: 1.插入到链表头部 2.插入到链表尾部 3.插入到空链表中 4.插入到链表内部 #include <stdio ...

随机推荐

  1. ansible非root用户批量修改root密码

    前言: 由于线上服务器密码长久没有更新,现领导要求批量更换密码.线上的之前部署过salt,但由于各种因素没有正常使用. 使用自动化工具批量修改的计划搁浅了,后来领导给了个python多线程修改密码脚本 ...

  2. html特殊字符的html,js,css写法汇总

    ⇠  箭头类 符号 UNICODE 符号 UNICODE HTML JS CSS HTML JS CSS ⇠ &#8672 \u21E0 \21E0 ⇢ &#8674 \u21E2 \ ...

  3. 链表与Hash检索实测

    测试环境: Win7 SP1.8G内存.3.4GHz 4核 测试代码: using System; using System.Collections.Generic; using System.Lin ...

  4. j2ee开源项目——IT学习者博客&lpar;itxxzblog v1&period;0&rpar;

    大家好,我是IT学习者-螃蟹,已经有近一周的时间没有更新文章了,作为回报,今天起将更新一个大件,也就是螃蟹还在进行中的IT学习者博客. IT学习者博客的初期设计已经完成,功能也已经完成了大半,具备了当 ...

  5. nodejs后台集成富文本编辑器(ueditor)

    1 下载ueditor nodejs版本 2 复制public目录下面的文件 到项目静态资源public文件夹下 3 在项目根目录创建ueditor文件夹 要复制进来的内容为 4 在根目录的 uedi ...

  6. 网络基础tcp&sol;ip协议二

    物理层解析: 物理层是TCP/IP模型的最低层,物理层为数据提供数据传输可靠通路. 物理层关心的介质: 信号 接口 传输介质 信号的分类:(信号是信息传递的媒介.) 模拟信号:连续变化的物理量 数字信 ...

  7. 纯CSS下拉菜单(希望对有需要的小伙伴有所帮助)

    效果截图(颜色有点丑,请无视): <!DOCTYPE html> <html> <head> <meta charset="utf-8" ...

  8. &num; RocEDU&period;课程设计2018 第三周进展 博客补交

    RocEDU.课程设计2018 第三周进展 博客补交 本周计划完成的任务 (1).本周计划完成在平板电脑上实现程序的功能,跟第二周计划完成任务基本相似. 本周实际完成情况 (1).实际完成情况还差最后 ...

  9. ArcGIS Server 服务器日志(待修改)

    有时遇到服务相关错误,需要查看日志来排查,这里简单写下日志相关操作. 服务器日志:http://resources.arcgis.com/zh-cn/help/main/10.2/index.html ...

  10. MySQL数据记录大小写敏感问题【转】

    MySQL大小写敏感 字符串大小写敏感和Mysql的数据库的名字.表名字.字段名字.还有字段值有关. 1.和数据库名字.表名字.存储过程和触发器有关 为0时:表示区分大小写,使用CREATE TABL ...