Why memory limit exceeded


  • 0
    J
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.empty()) return NULL;
        TreeNode *root = new TreeNode(preorder[0]);
        vector<int> preoderleft, preoderright,inorderleft,inorderright;
        int i =1, j=0;
        while(inorder[j]!=preorder[0]){
            preoderleft.push_back(preorder[i++]);
            inorderleft.push_back(inorder[j++]);
        }
        j++;
        while(j<inorder.size()){
            preoderright.push_back(preorder[i++]);
            inorderright.push_back(inorder[j++]);
        }
        root->left = buildTree(preoderleft,inorderleft);
        root->right = buildTree(preoderright,inorderright);
        return root;
    }

  • 1
    S

    Try avoiding creating new vectors in each recursive function call. Instead, always pass the original vectors in, but provide the range of subvectors as additional parameters. You can define a helper function that looks like this:

    TreeNode* buildTreeHelper(vector<int> &preorder, vector<int> &inorder, int pleft, int ileft, int length)
    

  • 0
    J

    Like @stellari said you can use the index, or you can just use the iterator like this:

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            return this->buildTreeEx(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
        }
        
        TreeNode *buildTreeEx(vector<int>::iterator preB, vector<int>::iterator preE, vector<int>::iterator inB, vector<int>::iterator inE) {
            if(preB==preE)
                return NULL;
            
            TreeNode *root = new TreeNode(*preB);
            int currentVal = *preB;
            preB++;
            
            if(preB==preE)
                return root;
            
            int tmpLen = 0;
            for(auto it=inB; it!=inE; it++) {
                if(*it==currentVal) {
                    root->left = buildTreeEx(preB, preB+tmpLen, inB, it);
                    root->right = buildTreeEx(preB+tmpLen, preE, it+1, inE);
                    break;
                }
                tmpLen++;
            }
            return root;
    
        }
    };

Log in to reply
 

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