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.

Have you met this question in a real interview? 

Yes

Example

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

其实做过怎么把sorted array变成 binary tree就知道这个咋做了
回忆下array的做法

给个beg, end,求个中间数，那么中间数必然为root, 然后递归求左边subarrray和右边subarray的中间数，分别为其左右孩子，返回root.

那么对于linked list就不能那么任性的随便跳来跳去，必须严格遵循inorder的办法来遍历，这样才能实现o(n)的方法构筑，而且单链表跳来跳去也不可能。。。

所以trick在于，同样用beg, end来trace，但是要不停的update head. 因为是inorder,从左娃，中娃到又娃的时候head已经移到那里了。具体看代码

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        int count=countList(head);
        return helper(head, 0, count-1);
    }
    
    TreeNode* helper(ListNode*& head, int beg, int end){
        if (!head || beg>end)
            return 0;
        int mid=beg+(end-beg)/2;
        TreeNode* left=helper(head, beg,mid-1);
        TreeNode* root= new TreeNode(head->val);
        head=head->next;
        TreeNode* right= helper(head, mid+1, end);
        root->left=left;
        root->right=right;
        return root;
    }
    
    int countList(ListNode* head){
        int count=0;
        while(head){
            count++;
            head=head->next;
        }
        return count;
    }
};