Memory Limit Exceeded.. so sad...


  • 0
    J

    Am i using too much memory ?
    Or it's just the memory limit is too strict ?

    You don't really need to read the code to tell the memory i used..
    It all depends on the size of the tree.

      /**
         * Definition for binary tree
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         * 
         * so the max path must be in leaf node.
         * get all combination of two nodes' path sum
         * wrong....
         */
        public class Solution {
            HashMap<TreeNode,Integer> id;
            ArrayList<TreeNode> nodes;
            HashMap<TreeNode,TreeNode> cp;//child -> parent;
            public int maxPathSum(TreeNode root) {
                if(root==null){
                    return 0;
                }
                id=new HashMap<TreeNode,Integer>();
                nodes=new ArrayList<TreeNode>();
                cp=new HashMap<TreeNode,TreeNode>();
                Deque<TreeNode> q=new LinkedList<TreeNode>();
                q.offerFirst(root);
                //tranverse node lvl by lvl. give each node an integer.
                //root=0   root->left=1  root->right=2
                //id:node to integer
                //nodes:integer to node
                //cp:child to parent.
                while(q.peekFirst()!=null){
                    TreeNode c=q.pollFirst();
                    if(c.left!=null) {q.offerLast(c.left);cp.put(c.left,c);}
                    if(c.right!=null) {q.offerLast(c.right);cp.put(c.right,c);}
                    id.put(c,nodes.size());
                    nodes.add(c);
                }
                
                //graph[i][j] means  from i to j's path value.
                int[][] graph=new int[nodes.size()][nodes.size()];
                int max=root.val;
                for(int i=0;i<nodes.size();i++){
                    
                    TreeNode c=nodes.get(i);
                    graph[i][i]=c.val;
                    //graph[i][id.get(c.left)]=c.val+c.left.val;
                    //find parent row. update this row according to parent row.
                    for(int m=0;m<i;m++){//connect this one with ones already added.
                        if(!cp.containsKey(c)){ break;}//this is the root
                        TreeNode p=cp.get(c);
                        graph[i][m]=graph[id.get(p)][m]+c.val;
                        graph[m][i]=graph[i][m];
                        max= (max>graph[i][m])?max:graph[i][m];
                    }
                }
                
                return max;
            }
        }

  • 0
    L

    If you need two maps, one list, one queue, and one 2D-array to solve a problem on a tree, you are most likely not doing the right thing. Have you tried a recursive version first?


  • 0
    J

    You're right i should do that. I'll be more careful on questions like these.
    should consider recursion first.

    Just curious about the mle. I mean i've seen other people's answers using similar structures so i just want to try it out..seems doesn't work here so well.


  • 0
    G

    Here is a recursive answer:

    the key is the int maxSum() in which maxSinglePath means the path with the max number which started from your current node (root here), and the return is the maxPath in the sub trees (left or right). Then compare these values

    	int maxPathSum(TreeNode *root) {
        int maxSinglePath=0;
        return maxSum(root,maxSinglePath);
    }
    
    
    
    int maxSum(TreeNode *root, int& maxSinglePath) {
        if(!root) 
    	{
    		maxSinglePath=0;
    		return 0;
    	}
    
        if(!root->left && !root->right) 
    	{
    		maxSinglePath=root->val;
    		return root->val;
    	}
    
        int maxRet=0; 
    
    	int maxLeft=0;
        int maxSingleLeft=0;
    
    	int maxRight=0;
        int maxSingleRight=0;
        
    	maxLeft=maxSum(root->left, maxSingleLeft);
    	maxRight=maxSum(root->right,maxSingleRight);
    
    	maxSinglePath=max(max(maxSingleLeft+root->val,root->val), max(maxSingleRight+root->val,root->val));
    	maxRet=max(max(maxSingleLeft+root->val,maxSingleLeft+maxSingleRight+root->val), max(maxSingleRight+root->val,maxSingleLeft+maxSingleRight+root->val));
    	maxRet=max(maxRet,root->val);
    
    	if(root->left)
    	{
    		maxRet=max(maxRet,maxLeft);
    	}
    
    	if(root->right)
    	{
    		maxRet=max(maxRet,maxRight);
    	}
    
        return maxRet;
    }

Log in to reply
 

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