首页 > 代码库 > [leetcode] Convert Sorted List to Binary Search Tree
[leetcode] Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
主要问题是链表中间节点不易获得。
思路1：链表转化成数组，然后上题做法。需要额外O(N)空间。
思路2：每次都从头找到中间节点，时间复杂度为O(NlogN)。
思路3：换一个思路，这次不top-down，而是bottom-up来做。一遍遍历链表，一遍中序遍历的顺序构建二叉树。
public class Solution { public TreeNode sortedListToBST(ListNode head) { int len = 0; ListNode p = head; while (p != null) { len++; p = p.next; } ListNode[] wrap = new ListNode[1]; wrap[0] = head; return SLtoBST(wrap, 0, len); } private TreeNode SLtoBST(ListNode[] wrap, int start, int end) { if (start >= end) return null; int mid = start + (end - start) / 2; TreeNode left = SLtoBST(wrap, start, mid); TreeNode root = new TreeNode(wrap[0].val); root.left = left; wrap[0] = wrap[0].next; root.right = SLtoBST(wrap, mid + 1, end); return root; } public static void main(String[] args) { ListNode head = ListUtils.makeList(1); TreeNode root = new Solution().sortedListToBST(head); }}
参考：
http://www.cnblogs.com/feiling/p/3267917.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。