Memory Limit Exceeded. Please help me.


  • 0
    S

    Given inorder and postorder traversal of a tree, construct the binary tree.

     class Solution {
      public:
    TreeNode* construct(TreeNode* root, int i, vector<int> postorder, vector<int> inorder) {
    	
    	if (inorder.size() == 0)
    		return NULL;
    	if (!root) {
    		root = new TreeNode(postorder[i]);
    	}
    	auto pos = find(inorder.begin(), inorder.end(), postorder[i]) - inorder.begin();
    	vector<int> left;
    
    	//RIGHT SUBTREE
    	vector<int> right;
    	for (auto i = pos + 1; i < inorder.size(); i++) {
    		right.push_back(inorder[i]);
    	}
    
    	if (right.size() == 1)
    		root->right = new TreeNode(right[0]);
    
    	else if (right.size() > 1)
    		root->right = construct(root->right, i - 1, postorder, right);
    
    	//LEFT SUBTREE
    	for (auto i = 0; i < pos; i++) {
    		left.push_back(inorder[i]);
    	}
    	if (left.size() == 1)
    		root->left = new TreeNode(left[0]);
    
    	else if (left.size() > 1)
    		root->left = construct(root->left, i - 1, postorder, left);
    
    	return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        TreeNode* root = NULL;
        if(!postorder.size())
            return NULL;
        if(postorder.size()==1)
        {
            root=new TreeNode(postorder[0]);
            return root;
        }
    	
    	int i = postorder.size() - 1;
    	auto pos = find(inorder.begin(), inorder.end(), postorder[i]) - inorder.begin();
    	
    	//RIGHT SUBTREE
    	vector<int> in;
    	
    	for (auto i = pos; i <inorder.size(); i++) {
    		in.push_back(inorder[i]);
    	}
    	root = construct(root, i, postorder, in);
    	
    	
    	//LEFT SUBTREE
    	
    	for (auto i = 0; i < in.size(); i++) {
    		postorder.erase(std::remove(postorder.begin(), postorder.end(), in[i]), postorder.end());
    	}
    	in.clear();
    	for (auto i = 0; i < pos; i++) {
    		in.push_back(inorder[i]);
    	}
    	i = postorder.size() - 1;
    	root->left = construct(root->left, i, postorder, in);
    	return root;
    }
    

    };


Log in to reply
 

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