image.png

题解一：类似二分查找，借助快慢指针找中点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head){
        if(head == NULL) return NULL;
        return helper(head,NULL);
    }
private:
    ListNode* findMidNode(ListNode* head, ListNode* tail){
        if(head == tail) return NULL;
        if(head->next == tail) return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != tail && fast->next != tail){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    TreeNode* helper(ListNode* head, ListNode* tail){
        if(head == tail) return NULL;
        if(head->next == tail) return new TreeNode(head->val);
        ListNode* mid = findMidNode(head, tail);
        ListNode* right = mid->next;
        TreeNode* root = new TreeNode(mid->val);
        cout<<mid->val<<endl;
        root->left = helper(head,mid);
        root->right = helper(right, tail);
        return root;
    }
};

题解二：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if(head == NULL) return NULL;
        return helper(head,  NULL);
    }
private:
    TreeNode* helper(ListNode* head, ListNode* tail){
        if(head == tail) return NULL;
        if(head->next == tail) return new TreeNode(head->val);
        ListNode* mid = head, *fast = head;
        while(fast != tail && fast->next != tail){//要注意这里是 *!= tail*
            mid = mid->next;
            fast = fast->next->next;
        }
        TreeNode* root = new TreeNode(mid->val);
        cout<<mid->val<<endl;
        root->left = helper(head, mid);
        root->right = helper(mid->next, tail);
        return root;
    }
};