java如何将有序链表转换二叉搜索树

发布时间:2022-01-17 14:35:36 作者:清风
来源:亿速云 阅读:127

这篇“java如何将有序链表转换二叉搜索树”文章,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要参考一下,对于“java如何将有序链表转换二叉搜索树”,小编整理了以下知识点,请大家跟着小编的步伐一步一步的慢慢理解,接下来就让我们进入主题吧。

给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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如何将有序链表转换二叉搜索树”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

推荐阅读:
  1. Java如何将Excel转换成PDF
  2. java如何将pdf转换成image

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java

上一篇:java中递归的示例分析

下一篇:vue如何用Echarts画柱状图

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》