1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

//in: head = [-10,-3,0,5,9]
//out: [0,-3,9,-10,null,5]
TreeNode *buildTree1(ListNode *head, ListNode *tail) {
    //递归边界，head==tail
    if (head == tail)   return nullptr;
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast != tail && fast->next != tail) {
        slow = slow->next;
        fast = fast->next->next;
    }
    TreeNode *root = new TreeNode(slow->val);//双指针找到中间结点
    root->left = buildTree(head, slow);
    root->right = buildTree(slow->next, tail);
    return root;
}
TreeNode* sortedListToBST1(ListNode* head) {
    return buildTree1(head, nullptr);
}


//vector
TreeNode *buildTree2(vector<int> v, int begin, int end){
    if (begin == end)   return nullptr;
    int mid = (begin+end)/2;
    TreeNode *root = new TreeNode(v[mid]);
    root->left = buildTree1(v, begin, mid);
    root->right = buildTree1(v, mid+1, end);
    return root;
}
TreeNode* sortedListToBST2(ListNode* head) {
    vector<int> vec;
    while (head != nullptr) {
        vec.push_back(head->val);
        head = head->next;
    }
    return buildTree2(vec, 0, vec.size());
}