您好,登录后才能下订单哦!
这篇“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主要应用于:1. web开发;2. Android开发;3. 客户端开发;4. 网页开发;5. 企业级应用开发;6. Java大数据开发;7.游戏开发等。
以上是“java如何将有序链表转换二叉搜索树”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。