Java BFS using Stack : Memory Limit Exceeded


  • 0
    R

    Can anybody help me figure out why does it say Memory Limit Exceeded,
    I am using one Stack and one ArrayList for the List to be returned. I did see some solutions using
    two queues, one solution using a LinkedList, so why does it disallow mine ?

     public List<Integer> rightSideView(TreeNode root) {
            List<Integer> num = new ArrayList<Integer>();
            if(root==null||root.right==null)return null;
            else{
                num.add(root.val);
                root=root.right;
                Stack<TreeNode> s = new Stack<TreeNode>();
                s.push(root);
                while(!s.isEmpty()){
                    TreeNode node = s.peek();
                    if(node.left!=null)s.push(node.left);
                    if(node.right!=null)s.push(node.right);
                    num.add(node.val);
                    s.pop();
            }
            return num;
        }
        }

  • 2
    I

    Assume the tree is:

       1
     /   \
    2     3
    

    First, you add the root to num and s.

    num: 1
    s:   1
    

    Second, run into the while loop.
    Push children in s.

    num: 1 1
    s:   1 2 3 (push 2,3)
    

    And pop top in s.

    num: 1 1
    s:   1 2 (pop 3)
    

    Third, the next loop, push nothing and pop 2 in s.

    num: 1 1 2
    s:   1
    

    Fourth, now the s is the same as first step.
    And then is:

    4:
    num: 1 1 2 1
    s:   1 2 (push 2,3 pop 3)
    
    5:
    num: 1 1 2 1 2
    s:   1 (pop 2)
    
    6:
    num: 1 1 2 1 2 1
    s:   1 2 (push 2,3 pop 3)
    
    ......
    
    Loop never end.  
    

    Now do you know why you are wrong?
    Your program will never end and get 'Time Limit Exceeded'. But before that the num will increase unlimitedly and course 'Memory Limit Exceeded'.
    In one word, your s.pop() is in wrong position.

    I think you can try to learn how to step debug Java.
    It will help you a lot.


  • 0
    I

    Oh, the num's add is also some problems.


Log in to reply
 

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