109.Convert Sorted List to Binary Search Tree

解题思路

题目的意思是将一个有序链表转换成一棵高度平衡的二叉搜索树
在108题Convert Sorted Array to Binary Search Tree
是将一个有序的数组转成一棵高度平衡的二叉搜索树，对于有序数组，我们可以常数时间内获取到mid位置的值
因此就可以非常方便的构建高度平衡的BST，
现在给定的不在是有序数组，而是链表，我们无法在常数时间内获取给定位置上的值，因为需要有一些其他的解决方案。

方案一

可以空间换时间，将链表转换成数组，然后根据数组构建Height balancedBST
时间复杂度： O(N) N表示链表长度
空间复杂度： O(N)
这个方法java的时间大概是2ms-3ms,击败了11.52%，代码如下

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
    	 ListNode tempHead = head;
    	 int count =0;
    	 while(tempHead != null){
    		 count++;
    		 tempHead = tempHead.next;
    	 }
    	 int []nums = new int[count];
    	 count =0;
    	 while(head != null){
    		 nums[count++] = head.val;
    		 head = head.next;
    	 }
    	 return buildBST(nums, 0, nums.length-1);  
    }
	private TreeNode buildBST(int []nums,int left,int right){
		if(left > right ) return null;
		if(left == right){
			return new TreeNode(nums[left]);
		}
		int mid = (left + right)/2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = buildBST(nums, left, mid-1);
		root.right = buildBST(nums, mid+1, right);
		return root;
	}
}

方案二

为了节省空间，我们可以专门写一个函数，用于返回给定节点以及其后若干位置上的节点引用。
时间复杂度：O(NlogN)  
空间复杂度：O(logN) 递归深度
java代码时间大概是: 2ms - 3ms 击败了11.52%
（和上面方法完全一样，感觉leetcode上的时间不是很精确，不过总体的分布还是可以参考的）

public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
		if(head == null)return null;
		int len = listLen(head);
		if(len ==1)return new TreeNode(head.val);
		return buildBST(head,0,len-1);
	}
	TreeNode buildBST(ListNode list,int begin, int end){
		if(begin > end){
			return null;
		}
		if(begin == end){
			return new TreeNode(list.val);
		}
		int mid = (begin+end)/2;
		ListNode midNode  = findMid(list, mid-begin);
		TreeNode root = new TreeNode(midNode.val);
		root.left = buildBST(list, begin, mid-1);
		root.right = buildBST(midNode.next, mid+1, end);
		return root;
	}
	/**	 * 返回head开始的第cur个点。	 * @param head	 * @param cur	 * @return	 */
	 * 返回head开始的第cur个点。
	 * @param head
	 * @param cur
	 * @return
	 */
	ListNode findMid(ListNode head,int cur){
		if(cur ==0)return head;
		int c =0;
		while(c < cur){
			head = head.next;
			c++;
		}
		return head;
	}
	int listLen(ListNode root){
		int c=0;
		if(root == null)return c;
		while(root!=null){
			c++;
			root = root.next;
		}
		return c;
	}

方案三

注意，一棵BST的中根遍历也是有序的。
假设一棵Height balanced BST如下：
     3
  1     5
0   2  4  6
中根遍历是： 0 1 2 3 4 5 6 （将这些数组成一个list）
也就是说，当进行中根遍历的时候，我们第一个访问的节点是list中的第一个数，也就是0，然后是1，然后是2，
（list是我们已经获取的中根遍历的节点顺序，我们只要按照顺序依次处理各个结点就可以了）
于是我们可以将0返回作为下一个结点的左子树，然后将2返回，作为1节点的右子树，
最后将此时的1返回。然后继续访问下一个结点就是3，返回的1作为3的左子树。
时间复杂度是 O(N)
空间复杂度是 O(logN)
提交java时间范围在1ms-2ms 之间，击败47.5% （我使用python求解，时间是304ms，20.59%）

ListNode node;
 public TreeNode sortedListToBST3(ListNode head) {
   // List<Integer> list = new ArrayList<>();
    ListNode tempHead = head;
    int count =0;
    while(tempHead != null){
          count++;
          tempHead = tempHead. next;
    }
    node = head;
    return buildBST3 (0,count-1);
 }
 public TreeNode buildBST3 (int begin,int end){
   if(begin > end) return null;
   int mid = (begin + end)/2;
   TreeNode left = buildBST3 (begin, mid-1);
   TreeNode root = new TreeNode( node. val);
   root.left = left;
   node = node.next;
   root.right = buildBST3 (mid+1,end);
   return root;
 }