java如何将有序链表转换二叉搜索树
这篇“java如何将有序链表转换二叉搜索树”文章，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要参考一下，对于“java如何将有序链表转换二叉搜索树”，小编整理了以下知识点，请大家跟着小编的步伐一步一步的慢慢理解，接下来就让我们进入主题吧。
目前创新互联已为1000+的企业提供了网站建设、域名、雅安服务器托管、网站改版维护、企业网站设计、蒙山网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
答案：
1public TreeNode sortedListToBST1(ListNode head) {
2 if (head == null) return null;
3 return toBST(head, null);
4}
5
6public TreeNode toBST(ListNode head, ListNode tail) {
7 ListNode slow = head;
8 ListNode fast = head;
9 if (head == tail) return null;
10
11 while (fast != tail && fast.next != tail) {
12 fast = fast.next.next;
13 slow = slow.next;
14 }
15 TreeNode thead = new TreeNode(slow.val);
16 thead.left = toBST(head, slow);
17 thead.right = toBST(slow.next, tail);
18 return thead;
19}
解析：
这题比较简单，因为我们已知链表是有序的，要想转化为高度平衡的二叉树，我们只需要用排序链表的中间节点当做二叉树的根节点，前面部分作为二叉树的左子树，后面部分作为二叉树的右子树，然后在以同样的方式分别递归左右子树即可。再来换种写法
1public TreeNode sortedListToBST(ListNode head) {
2 if (head == null)
3 return null;
4 if (head.next == null)
5 return new TreeNode(head.val);
6 ListNode slow = head, pre = null, fast = head;
7 while (fast != null && fast.next != null) {
8 pre = slow;
9 slow = slow.next;
10 fast = fast.next.next;
11 }
12 pre.next = null;
13 TreeNode n = new TreeNode(slow.val);
14 n.left = sortedListToBST(head);
15 n.right = sortedListToBST(slow.next);
16 return n;
17}
其实思路还都是一样的，其中第12行是相当于把链表两边的前后两部分断开。slow成为当前节点，slow的前部分变成当前节点的左子树，slow的后半部分变成当前节点的右子树。
Java可以用来干什么
Java主要应用于：1. web开发；2. Android开发；3. 客户端开发；4. 网页开发；5. 企业级应用开发；6. Java大数据开发；7.游戏开发等。
以上是“java如何将有序链表转换二叉搜索树”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！
网站名称：java如何将有序链表转换二叉搜索树
分享URL：http://ybzwz.com/article/podpcp.html
