这篇文章主要介绍了LeetCode如何实现二叉搜索树与双向链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。比如，输入下图中的二叉搜索树，输出转换之后的排序双向链表。
二叉树节点的定义如下：
计算
安全
数据库
网络和加速
企业服务
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}众所周知，中序遍历二叉搜索树会得到有序的序列，我们目标是在中序遍历二叉搜索树过程中，逐步将其转换成有序的双向链表。另外，将树节点的左子树指针转换成双向链表节点的前驱指针，而树节点的右子树指针转换成双向链表节点的后驱指针。
import com.lun.util.BinaryTree.TreeNode;
public class ConvertBSTToLinkedList {
private TreeNode last;//用于指向双向链表的尾节点
public TreeNode convert(TreeNode root) {
convertNode(root);
TreeNode head = last;
while(head != null && head.left != null) {
head = head.left;
}
return head;
}
private void convertNode(TreeNode node) {
if(node == null) {
return;
}
TreeNode current = node;
if(current.left != null) {
convertNode(current.left);
}
current.left = last;//1.执行到这步，左子树已经转换成有序双向链表
if(last != null) {
last.right = current;//2.
}
last = current;//3.current转换成有序双向链表的新尾节点
if(current.right != null) {
convertNode(current.right);
}
}
}import org.junit.Assert;
import org.junit.Test;
import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;
public class ConvertBSTToLinkedListTest {
@Test
public void test() {
ConvertBSTToLinkedList cbl = new ConvertBSTToLinkedList();
TreeNode root = makeABST();
TreeNode head = cbl.convert(root);
Assert.assertEquals("4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> \n" +
"16 -> 14 -> 12 -> 10 -> 8 -> 6 -> 4 -> ", printList(head));
}
private TreeNode makeABST() {
int[] array = {10, 6, 14, 4, 8, 12, 16};
return BinaryTree.integerArray2BinarySearchTree(array);
}
private String printList(TreeNode head) {
String result = "";
TreeNode p = head;
while(true) {
result += (p.val + " -> ");
if(p.right == null) {
break;
}
p = p.right;
}
result += "\n";
while(p != null) {
result = result + p.val + " -> ";
p = p.left;
}
return result;
}
}感谢你能够认真阅读完这篇文章，希望小编分享的“LeetCode如何实现二叉搜索树与双向链表”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/jallenkwong/blog/4613225
