[LeetCode]Convert Sorted List to BST

第一种做法类似把 array 变成 BST 的做法，但这里因为是list，所以我们要扫一遍来找到中点，时间复杂度 O(n log n)，代码如下：

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; next = null; }
	* }
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
	if (head == null)
	return null;
	int len = 0;
	ListNode curr = head;
	while (curr != null) {
	curr = curr.next;
	len++;
	}
	return recursion(head, 0, len - 1);
	}
	private TreeNode recursion(ListNode head, int lo, int hi) {
	if (lo > hi)
	return null;
	int mid = lo + (hi - lo) / 2;
	int count = 0;
	ListNode curr = head;
	while (count < mid) {
	count++;
	curr = curr.next;
	}
	TreeNode node = new TreeNode(curr.val);
	node.left = recursion(head, 0, mid - 1);
	node.right = recursion(curr.next, 0, hi - mid - 1);
	return node;
	}
	}

view raw covert sorted list to BST v-1.java hosted with ❤ by GitHub

第二种方法 check here，简而言之就是按照 inorder 的顺序构建 BST，这样 list 也一步一步向后移就可以了，时间复杂度 O(n)，代码如下：

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; next = null; }
	* }
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	ListNode curr;
	public TreeNode sortedListToBST(ListNode head) {
	curr = head;
	int len = 0;
	ListNode curr = head;
	while (curr != null) {
	len++;
	curr = curr.next;
	}
	return build(0, len - 1);
	}
	private TreeNode build(int lo, int hi) {
	if (lo > hi)
	return null;
	int mid = lo + (hi - lo) / 2;
	TreeNode left = build(lo, mid - 1);
	TreeNode node = new TreeNode(curr.val);
	curr = curr.next;
	TreeNode right = build(mid + 1, hi);
	node.left = left;
	node.right = right;
	return node;
	}
	}

view raw covert sorted list to BST v-2.java hosted with ❤ by GitHub