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

时间:2021-11-06 09:06:15

题目

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

给定一个二叉查找树:

    4
/ \
2 5
/ \
1 3

返回 1<->2<->3<->4<->5

解题

/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* Definition for Doubly-ListNode.
* public class DoublyListNode {
* int val;
* DoublyListNode next, prev;
* DoublyListNode(int val) {
* this.val = val;
* this.next = this.prev = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of tree
* @return: the head of doubly list node
*/ public DoublyListNode bstToDoublyList(TreeNode root) {
// Write your code here
if(root == null)
return null;
DoublyListNode Root = new DoublyListNode(root.val);
if(root.left==null && root.right==null){
return Root;
}
DoublyListNode left = bstToDoublyList(root.left);
DoublyListNode tmpLeft = left;
while(tmpLeft!=null && tmpLeft.next!=null){
tmpLeft = tmpLeft.next;
}
if(left!=null){
tmpLeft.next = Root;
Root.prev = tmpLeft;
}
DoublyListNode right = bstToDoublyList(root.right);
if(right!=null){
Root.next = right;
right.prev = Root;
}
return left!=null?left:Root;
}
}

lintcode:将二叉查找树转换成双链表的更多相关文章

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

    将二叉查找树转换成双链表 将一个二叉查找树按照中序遍历转换成双向链表. 样例 给定一个二叉查找树: 返回 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. BZOJ 3158&colon; 千钧一发

    3158: 千钧一发 Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 1201  Solved: 446[Submit][Status][Discuss ...

  2. thinkphp pathinfo nginx 无法加载模块&colon;Index

    thinkphp 报了 无法加载模块:Index 错误位置 FILE: /var/multrix/wxactivity_archive/ThinkPHP/Library/Think/Dispatche ...

  3. 使用SecureCRT远程链接Ubuntu出现 Change of username or service not allowed的问题

    RT:    首先是确认ubuntu上有运行 sshd服务的 但是用SecureCRT链接时报错,默认用户名是root: 打开ssh_config检查下是否禁止直接用root登陆 这句 改成yes o ...

  4. phpcms调用某个栏目下的所有二级栏目

    在html中直接这样调用就可以了,subcat中的值为父栏目的catid {loop subcat(93) $r}{/loop} 注意subcat方法的参数,如果只写一个参数,也就是父栏目id,那该父 ...

  5. Orchard用LiveWriter写博客

    本文链接:http://www.cnblogs.com/souther/p/4544241.html Orchard本身提供一个内建的管理面板来写博客,许多人更喜欢采用客户端提交的方式,例如Windo ...

  6. 记录近期小改K-Means至MapReduce上的心得

    背景: 在所有聚类算法中KMeans算是表面上最简单的一种,没有过多恼人的古希腊符号公式,没有过分繁杂的公式嵌套.对于一个初学矩阵或者仅有向量概念的非专业人士的来说,不可不畏是一把踹门利器.这个世界上 ...

  7. Ubuntu 11&period;04 NFS 配置

    安装 NFS 相关组件 sudo apt-get install nfs-kernel-server 增加 NFS 目录 sudo gedit /etc/exports #在文件中添加如下内容 /va ...

  8. Jmeter 非 GUI 命令行执行脚本文件

    https://www.cnblogs.com/yebaofang/p/9803273.html

  9. python - classs内置方法 solt

    solt # __solt__ # 是一个类变量,变量值可以是列表.元组或者是可迭代对象,也可以是一个字符串 # (以为这所有实例只有一种数据属性) # # 作用:(为了节省内存空间,减少过多的实例属 ...

  10. &lpar;Java&rpar;怎么去掉字符串数组中重复的值?

    String fdbs = "WXB,WXA,FDA,WXB"; String[] str = fdbs.split(","); Set set = new H ...