Why Memory Limit Exceeded for this code


  • 0
    C
    /**
     * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.empty()||inorder.empty())
                return NULL;
            int rootVal = preorder[0];
            TreeNode *root = new TreeNode(rootVal);
            if(preorder.size()==1||inorder.size()==1){
                return root;
            }
            vector<int> preorderLeft;
            preorderLeft.clear();
            vector<int> preorderRight;
            preorderRight.clear();
            vector<int> inorderLeft;
            inorderLeft.clear();
            vector<int> inorderRight;
            inorderRight.clear();
            int count = 0;
            for(int i= 0;i < inorder.size();i++){
                if(inorder[i]==rootVal){
                    count = i;
                    break;
                }
                inorderLeft.push_back(inorder[i]);
            }
            for(int j = 1+count;j < inorder.size();j++){
                inorderRight.push_back(inorder[j]);
            }
            for(int k = 1;k <= count;k++){
                preorderLeft.push_back(preorder[k]);
            }
            for(int m = count+1;m < preorder.size();m++){
                preorderRight.push_back(preorder[m]);
            }
            TreeNode* left = buildTree(preorderLeft,inorderLeft);
            TreeNode* right = buildTree(preorderRight,inorderRight);
            root->left = left;
            root->right = right;
            return root;
        }
    };

  • 0
    W

    Each time you call this function you will create 4 vectors and fill them with 2*(n-1) items for n is the length of the order.

    And you will call this function n times , even n is getting smaller , the average length is n/2 , so you will cost memory of n*(n-1) * sizeof(int),this is huge when n is big.

    Why don't you consider to reuse or release the memory of vector before you recurse this function?


  • 0
    C

    I see, it means each time I recuse invoke this function, the vector will be recreated, then the whole stack for storing all these vectors will be large.


Log in to reply
 

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