Problem
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example
21->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; }}