Why my code Memory Limit Exceeded?


  • 0
    L
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    	int i, n;
    	n = inorder.size();
    	if (0 == n)
    		return NULL;
    	for (i = 0; i < n; i++)
    	{
    		if (inorder[i] == postorder[n - 1])
    			break;
    	}
    	vector<int> linorder(inorder.begin(), inorder.begin()+i);
    	vector<int> rinorder(inorder.begin()+i+1, inorder.end());
    	vector<int> lpostorder(postorder.begin(), postorder.begin()+i);
    	vector<int> rpostorder(postorder.begin()+i, postorder.end()-1);
    	TreeNode *root = new TreeNode(postorder[n-1]);
    	root->left = buildTree(linorder, lpostorder);
    	root->right = buildTree(rinorder, rpostorder);
    	return root;
    }

  • 0
    J

    This solution will construct many vectors which may consume lots of memory on the stack.


  • 0
    T

    You can do the same job using a helper function that manipulates iterators to avoid the extra space overhead.


  • 0
    K

    after creating linorder, rinorder, lpostorder and rpostorder you must free the memory allocated to the original vectors. It can be done by

    inorder.clear();
    inorder.shrink_to_fit();

    this would deallocate the space being used by inorder vector.


Log in to reply
 

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