Why am I getting a StackOverFlow error for Stack.pop() method?


  • 0
    S

    I'm using two Stacks, one for the original graph one for the cloned one. A HashSet is used to keep the visited nodes.

    I got StackOverFlow error on line: UndirectedGraphNode cur = s1.pop(); I'm too confused by this error. Can anyone please help me figure out why is so?

    Here is my code:

    /**
     * Definition for undirected graph.
     * class UndirectedGraphNode {
     *     int label;
     *     List<UndirectedGraphNode> neighbors;
     *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
     * };
     */
     
     import java.util.Stack;
     import java.util.HashSet;
    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node == null){
                return null;
            }
            UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
            Stack<UndirectedGraphNode> s1 = new Stack<UndirectedGraphNode>();
            Stack<UndirectedGraphNode> s2 = new Stack<UndirectedGraphNode>();
            HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
            s1.push(node);
            s2.push(newNode);
            cloneGraph2(s1, s2, visited);
            return newNode;
        }
        
        private void cloneGraph2(Stack<UndirectedGraphNode> s1, Stack<UndirectedGraphNode> s2, HashSet<UndirectedGraphNode> visited){
            if(s1.empty() || s2.empty()){
                return;
            }
            UndirectedGraphNode cur = s1.pop();
            UndirectedGraphNode newCur = s2.pop();
            if(!visited.contains(cur)){
                visited.add(cur);
                List<UndirectedGraphNode> neighbors = cur.neighbors;
                List<UndirectedGraphNode> newNeighbors = new ArrayList<UndirectedGraphNode>();
                for (UndirectedGraphNode item: neighbors){
                    
                    if (item.label == cur.label){ //if the node points at itself
                        newNeighbors.add(newCur);
                        continue;
                    }
                    
                   
                    else {
                            UndirectedGraphNode newNode = new UndirectedGraphNode(item.label);
                            newNeighbors.add(newNode);
                                s1.push(item);
                                s2.push(newNode);
                            
                        }
                }
                
                newCur.neighbors = newNeighbors;    
            }
            
            cloneGraph2(s1, s2, visited);
        }
    }

  • 1
    F

    Your recursion have too many levels for some test cases, try to write this code non recursion.


  • 0
    S

    I see the problem. Thanks!

    The error StatckOverFlow didn't come from the Stacks in my code but the JVM's Stack.


Log in to reply
 

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