题目
将一个二叉查找树按照中序遍历转换成双向链表
给定一个二叉查找树:
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:将二叉查找树转换成双链表的更多相关文章
-
LintCode-378.将二叉查找树转换成双链表
将二叉查找树转换成双链表 将一个二叉查找树按照中序遍历转换成双向链表. 样例 给定一个二叉查找树: 返回 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 ...
随机推荐
-
BZOJ 3158: 千钧一发
3158: 千钧一发 Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1201 Solved: 446[Submit][Status][Discuss ...
-
thinkphp pathinfo nginx 无法加载模块:Index
thinkphp 报了 无法加载模块:Index 错误位置 FILE: /var/multrix/wxactivity_archive/ThinkPHP/Library/Think/Dispatche ...
-
使用SecureCRT远程链接Ubuntu出现 Change of username or service not allowed的问题
RT: 首先是确认ubuntu上有运行 sshd服务的 但是用SecureCRT链接时报错,默认用户名是root: 打开ssh_config检查下是否禁止直接用root登陆 这句 改成yes o ...
-
phpcms调用某个栏目下的所有二级栏目
在html中直接这样调用就可以了,subcat中的值为父栏目的catid {loop subcat(93) $r}{/loop} 注意subcat方法的参数,如果只写一个参数,也就是父栏目id,那该父 ...
-
Orchard用LiveWriter写博客
本文链接:http://www.cnblogs.com/souther/p/4544241.html Orchard本身提供一个内建的管理面板来写博客,许多人更喜欢采用客户端提交的方式,例如Windo ...
-
记录近期小改K-Means至MapReduce上的心得
背景: 在所有聚类算法中KMeans算是表面上最简单的一种,没有过多恼人的古希腊符号公式,没有过分繁杂的公式嵌套.对于一个初学矩阵或者仅有向量概念的非专业人士的来说,不可不畏是一把踹门利器.这个世界上 ...
-
Ubuntu 11.04 NFS 配置
安装 NFS 相关组件 sudo apt-get install nfs-kernel-server 增加 NFS 目录 sudo gedit /etc/exports #在文件中添加如下内容 /va ...
-
Jmeter 非 GUI 命令行执行脚本文件
https://www.cnblogs.com/yebaofang/p/9803273.html
-
python - classs内置方法 solt
solt # __solt__ # 是一个类变量,变量值可以是列表.元组或者是可迭代对象,也可以是一个字符串 # (以为这所有实例只有一种数据属性) # # 作用:(为了节省内存空间,减少过多的实例属 ...
-
(Java)怎么去掉字符串数组中重复的值?
String fdbs = "WXB,WXA,FDA,WXB"; String[] str = fdbs.split(","); Set set = new H ...