28ms,easy-understand c++ solution


  • 2
    D
    enter code here
    class Solution {
    public:
    TreeNode* sortedListToBST(ListNode* head) {
        vector<int>nums;
        TreeNode *root;
        if(head==NULL) {
            return NULL;
        }
        while(head!=NULL) {
            nums.push_back(head->val);
            head=head->next;
        }
        sortedListToBST(nums,root,0,nums.size()-1);
        return root;
    }
    private:
    void sortedListToBST(vector<int>&nums,TreeNode *&root,int beginIndex,int endIndex) {
        if(beginIndex>endIndex) {
            root=NULL;
            return ;
        }
        int mid=(beginIndex+endIndex)/2;
        root=new TreeNode(nums[mid]);
        sortedListToBST(nums,root->left,beginIndex,mid-1);
        sortedListToBST(nums,root->right,mid+1,endIndex);
     }
    };

  • 0
    1
    TreeNode* sortedListToBST(ListNode* head) {
        if(head== NULL)
            return NULL;
        ListNode* dummy=new ListNode(-1);
        dummy->next = head;
        ListNode* fast= dummy;
        ListNode* slow = dummy;
        ListNode* pre = slow;
        //find middle node
        while(fast && fast->next)
        {
            fast= fast->next->next;
            pre = slow;
            slow= slow->next;
        }
        //r is the right list 
        ListNode* r = slow->next;
        pre->next= NULL;
        //l is the left list
        ListNode* l = dummy->next;
        delete dummy;
        TreeNode* root = new TreeNode(slow->val);
        root->left = sortedListToBST(l);
        root->right = sortedListToBST(r);
        return root;
    }
    

    This is how I solve it with C++;


  • 0
    N

    hi, maybe this is your correct code :)

    class Solution {
    public:
        TreeNode* sortedListToBST(ListNode* head) {
            if(head== NULL)
                return NULL;
            if(!head->next)
             return new TreeNode(head->val);
            ListNode* fast= head;
            ListNode* slow = head;
            ListNode* pre = slow;
            //find middle node
            while(fast && fast->next)
            {
                fast= fast->next->next;
                pre = slow;
                slow= slow->next;
            }
            //r is the right list 
            ListNode* r = slow->next;
            pre->next= NULL;
            //l is the left list
            ListNode* l = head;
            TreeNode* root = new TreeNode(slow->val);
            root->left = sortedListToBST(l);
            root->right = sortedListToBST(r);
            return root;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.