Why Memory Limit Exceeded ?


  • 0
    T

    When submit, memory limit exceeded. However, when run the case, it passed. What is wrong with my source code?

    // Encodes a tree to a single string.
    public string serialize(TreeNode root)
    {
        if( root == null ) return string.Empty;
       
       string res = root.val.ToString();
       Queue< TreeNode > queue = new Queue< TreeNode >();
        queue.Enqueue(root);
        while( queue.Count != 0 )
        {
            TreeNode node = queue.Dequeue();
            res += "," + ( node.left == null? "n":node.left.val.ToString() );
            res += "," + ( node.right == null? "n":node.right.val.ToString() );
            if( node.left != null ) queue.Enqueue(node.left);
            if( node.right != null ) queue.Enqueue(node.right);
        }
        
       int index = res.Length -1;
       
       while( index > 0 && res[index] == 'n' && res[index -1 ] == ',' )
       {
           index -= 2;
       }
       
       res = res.Substring( 0, index + 1 );
        
        return res;
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        TreeNode root = null;
        int index = data.IndexOf(",");
        if( index < 0 ) return root;
        
        root = new TreeNode( int.Parse(data.Substring( 0, index ) ) );
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        int startIndex = index + 1; int endIndex = startIndex;
        while( queue.Count != 0 )
        {
            TreeNode node = queue.Dequeue();
    
            endIndex = data.IndexOf(",", startIndex);
            if( endIndex == -1 ) endIndex = data.Length;
            
            string curValue = data.Substring( startIndex, endIndex - startIndex );
            
            node.left = curValue == "n" ? null: new TreeNode( int.Parse(curValue) );
            
            startIndex = endIndex + 1;
            if( startIndex >= data.Length ) break;
            
            endIndex = data.IndexOf(",",startIndex);
            if( endIndex == -1  ) endIndex = data.Length;
            
            curValue = data.Substring(startIndex,endIndex - startIndex);
            
            node.right = curValue == "n" ? null: new TreeNode(int.Parse(curValue));
            
            if( node.left != null ) queue.Enqueue(node.left);
            if(node.right != null ) queue.Enqueue(node.right);
            
            startIndex = endIndex + 1;
            if( startIndex >= data.Length ) break;
        }
        
        return root;
    }

  • 0
    H

    Even I tried with level order traversal but got TLE in serialize(). I had to go with pre-order traversal to get over it. But by the looks of it, you do use more memory in deseriaize() method. You don't need a queue to deserialize.


  • 0
    T

    Many thanks for your reply, it helps me optimizing the code.


Log in to reply
 

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