C++ solution deserialize from preorder and inorder, but finally MLE, does anyone have any idea?


  • 0
    L

    I use preorder and inorder sequence to construct a BST recursively . But it does Memory Limit Exceeded. Does anyone konw what's the problem?
    '''
    class Codec {
    public:

    void serializeCore(TreeNode *&root, string &s){
        if(root == nullptr){
            return;
        }
        if(root){
            char tmp[20];
    		sprintf(tmp,"%d ",root->val);
    		s.append(tmp);
        }
        serializeCore(root->left, s);
        serializeCore(root->right, s);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        serializeCore(root,res);
        return res;
    }
    
    TreeNode* deserializeCore(vector<int> preorder, int pre_left, int pre_right,
    	vector<int> inorder, int in_left, int in_right){
    		TreeNode* root = nullptr;
    		if(preorder.size()!=inorder.size()||pre_left>pre_right || in_left>in_right ){
    			return root;
    		}
    		root = new TreeNode(preorder[pre_left]);
    		int len = 0;
    		for(int i = in_left; i<=in_right; i++){
    			if(inorder[i] != preorder[pre_left]){
    				len++;
    			}else
    				break;
    		}
    		
    		root->left = deserializeCore(preorder, pre_left+1, 
    			pre_left+len, inorder,in_left, in_left+len-1);
    		root->right = deserializeCore(preorder, pre_left+len+1, 
    			pre_right, inorder, in_left+len+1, in_right);
    		return root;
    }
    
    TreeNode* deserialize(string preorder){
        vector<int> preorder_vec;
        int num = 0;
        for(int i=0; i<preorder.size(); i++){
            if(preorder[i] == ' '){
                preorder_vec.push_back(num);
                num = 0;
            }else
                num = num*10 + preorder[i]-'0';
        }
        vector<int> inorder_vec = preorder_vec;
    	sort(inorder_vec.begin(), inorder_vec.end());
    	TreeNode *root = deserializeCore(preorder_vec, 0, preorder_vec.size()-1, inorder_vec, 0, inorder_vec.size()-1);
    	return root;
    }
    

    };
    '''


Log in to reply
 

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