Problem

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Example

               2
1->2->3  =>   / \1   3

Note

用递归的方法来做，首先新建cur结点来复制head结点，然后计算链表head的长度，调用helper(start, end)函数建立平衡BST。
当链表为空时，helper()中出现start大于end，返回null。然后计算中点mid，以mid为界分别递归构建左右子树。顺序是，左子树-->根结点-->右子树。由于根节点root是直接取cur.val构建，当前的cur已经被取用。所以在下一次递归构建右子树之前，要让cur指向cur.next。最后将root和左右子树相连，返回root。

Solution

public class Solution {ListNode cur;public TreeNode sortedListToBST(ListNode head) {  cur = head;int len = 0;while (head != null) {head = head.next;len++;}return helper(0, len-1);}public TreeNode helper(int start, int end) {if (start > end) return null;int mid = start+(end-start)/2;TreeNode left = helper(start, mid-1);TreeNode root = new TreeNode(cur.val);cur = cur.next;TreeNode right = helper(mid+1, end);root.left = left;root.right = right;return root;}
}