LeetCode109_Convert Sorted List to Binary Search t题目tiTree(将链表转成二叉排序树) Java题解
2023-09-27 14:25:17 时间
题目:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
题解:将一个有序链表转成二叉排序树,假设是一棵相对平衡的排序树,应该是这种,链表中间那个节点为树的根节点。根节点的左子树节点应该是根节点左边那部分的中间节点,根节点的右节点应该是根节点右边那部分链表的中间节点,后面就依照这个规律依次类推了。
知道上面的规律之后,问题的关键点就是寻找一个链表的中间节点了,这个应该是非常熟悉的。用快慢两个指针能够轻松解决。
以下是这种思路的实现代码:
代码:
//相似归并排序 O(Nlogn) public static TreeNode sortedListToBST(ListNode head) { ListNode fast=head; ListNode slow=head; if(head==null)//递归结束条件 return null; ListNode leftOfMid=null;//用来记录中间节点的前一个节点。这里把slow指向的节点看做中间及诶单 while(fast.next!=null&&fast.next.next!=null) { fast=fast.next.next; leftOfMid=slow; slow=slow.next; } if(leftOfMid==null)//说明没有进入上面的while循环 说明这时候仅仅有1个或两个节点 这时候就不存在左链表的左半部分了 head=null; else leftOfMid.next=null;//假设有左半部分则把左半部分链表的末尾指向空,将链表截两段 ListNode rightOfMid=slow.next;//链表右半部分的開始 TreeNode root=new TreeNode(slow.val); root.left=sortedListToBST(head); root.right=sortedListToBST(rightOfMid); return root; }上面的时间复杂区是n*logn,有没有O(n)的算法呢,新建每个树节点一遍下来时间复杂度就是o(n)了,所以在寻找中间节点的时候仅仅能是常数时间,这样才干让终于的时间复杂度为O(n),这样仅仅能借助哈希表进行辅助了
代码:
//用哈希表O(n)时间复杂度 public static TreeNode sortedListToBST2(ListNode head) { Hashtable< Integer, TreeNode> hashtable=new Hashtable<>(); if(head==null) return null; ListNode cur=head; int length=0; while(cur!=null) { TreeNode node=new TreeNode(cur.val); hashtable.put(length,node ); cur=cur.next; length++; } return buildTree(0, length-1, hashtable); } public static TreeNode buildTree(int start,int end,Hashtable<Integer, TreeNode> hashtable) { if(start<=end) { int mid=(start+end)/2; TreeNode root=hashtable.get(mid); root.left=buildTree(start,mid-1 , hashtable); root.right=buildTree(mid+1, end, hashtable); return root; } else { return null; } }
相关文章
- Java 如何删除 List 中的重复元素
- nutch1.4 在windows下面提示 java.io.IOException: CreateProcess error=2, ϵͳÕҲ»µ½ָ¶
- Java-list,set,map的区别
- redis的安装和使用【2】redis的java操作
- Java从入门到放弃18---Map集合/HashMap/LinkedHashMap/TreeMap/集合嵌套/Collections工具类常用方法
- Java魔法堂:String.format详解
- Effective Java 第三版——49. 检查参数有效性
- java基础知识:多态
- GitHub公布10大热门编程语言:Java好猛
- Java RuntimeException异常处理汇总
- Java精选笔记_集合【List(列表)接口】
- java的应用包的方法,及调用类里面函数的原理
- 在Java中如何遍历Map对象
- java 循环中使用list时,出现list中全部加入了对象导致没有实现分组的解决方案
- java List转变为逗号分隔的字符串(字符串去重)
- Java中List和ArrayList的区别
- .pgr照片文件解析,C++与Java存储数据差别大小端模式
- Java读取批量Excel文件,并转化为List<Map<String,String>>
- 已解决java.lang.NoSuchMethodException: java.util.List.<init>()异常的正确解决方法,亲测有效!!!
- 已解决java.lang.NoClassDefFoundError异常的正确解决方法,亲测有效!!!
- 【Java 虚拟机原理】堆区 | Java VisualVM 工具
- Java集合类: Set、List、Map、Queue使用场景梳理
- Java socket中关闭IO流后,发生什么事?(以关闭输出流为例)
- Java中如何优雅地删除List中的元素
- java 复制 一个list 到另一个list
- Dota兄订餐——静态代理(java)
- 【Java基础系列】List,String,Set换转