[LeetCode 题解]:Convert Sorted List to Binary Search Tree

class Solution {
public:
    // find middle element of the list
    ListNode *getmiddleList(ListNode *left,ListNode *right){
        //omit the condition :  left!=right && left->next!=right
        ListNode *pre,*last;
        pre=left; last =left->next;
        while(last!=right){
            last = last->next;
            if(last!=right){
                last = last->next;
                pre=pre->next;
            }
        }
        return pre;
    }
    
    // retri-BST constructor
    TreeNode *getBST(ListNode *left,ListNode *right){
        TreeNode *root = new TreeNode(0);
        //no leaf 
        if(left==right) return NULL;
        // only one leaf
        if(left->next == right){
            root->val=left->val;
            return root;
        }
        //more than one leaf
        ListNode *middle =getmiddleList(left,right);
        root->val = middle->val;
        root->left = getBST(left, middle);
        root->right = getBST(middle->next,right);
        return root;
    }
    TreeNode *sortedListToBST(ListNode *head) {
        TreeNode* root= new TreeNode(0);
        if(head==NULL) return NULL;
        if(head->next==NULL){
            root->val=head->val;
            root->left=root->right=NULL;
            return root;
        }
        ListNode *left,*middle,*right;
        middle=left=head;
        right=head->next;
        while(right){
            right=right->next;
            if(right){
                right=right->next;
                middle=middle->next;
            }
        }
        root->val=middle->val;
        root->left = getBST(left, middle);
        root->right= getBST(middle->next,right);
        return root;
    }
};