Memory Limit Exceeded


  • 1
    H

    What's the memory limit?

    Do I need to delete all ListNode?

    Thats's my code:

    TreeNode *sortedListToBST(ListNode *head) {
        vector<TreeNode *> nodes;
        if(head == NULL){
            return NULL;
        }
        TreeNode * temp_tree = new TreeNode(head->val);
        nodes.push_back(temp_tree);
        while(head->next){
            ListNode * victim = head;
            head = head->next;
            delete victim;
            temp_tree = new TreeNode(head->val);
            nodes.push_back(temp_tree);
        }
        
        return make_tree(nodes, 0, nodes.size()-1);
    }
    
    TreeNode * make_tree(vector<TreeNode *> nodes, int head, int tail){
        int root_index = (head+tail)/2;
        if(tail <= head){
            return nodes[head];
        }else if(tail == head+1){
            nodes[head]->right = nodes[tail];
            return nodes[head];
        }else{
            nodes[root_index]->right = make_tree(nodes, root_index+1, tail-1);
            nodes[root_index]->left = make_tree(nodes, head, root_index-1);
            return nodes[root_index];
        }
    }

  • 3
    C

    No, you do not need delete listnode. can you explain your algorithm? I do not know why

    nodes[root_index]->right = make_tree(nodes, root_index+1, tail-1);
    

    why it is " tail -1 ", not " tail "?


  • 0
    H

    Sorry, that's one of my mistake, and it should be tail.
    The median of the list is the root of the BST, and recursively do the same process to the left part and the right part.
    This ALG is accepted when the input is a sorted array in another question and has MLE in this question, so I don't know why.


  • 0
    C

    I find your bug. TreeNode * make_tree(vector<TreeNode *> nodes, int head, int tail) should be TreeNode * make_tree(vector<TreeNode *> &nodes, int head, int tail). when this function is called, nodes will be copied, which waste a lot memory. So if it is reference, no copy is needed.


  • 0
    H

    It works! Thank you.


Log in to reply
 

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