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如何将有序链表转换二叉搜索树
文章源于：https://www.cdcxhl.com/article28/podpcp.html

成都网站建设公司_创新互联，为您提供网站营销、ChatGPT、网页设计公司、Google、网站改版、品牌网站设计

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联