Java Depth Search Accepted Solution


  • 1
    D

    Use a hashmap<oldNode,newNode> to record the visited node, in order to avoid circle.

    public class Solution {
        private HashMap<UndirectedGraphNode,UndirectedGraphNode> copied; 
        
        public UndirectedGraphNode dfs(UndirectedGraphNode node)
        {
            if(node==null)
                return null;
            if(copied.containsKey(node))
                return copied.get(node);
                
            UndirectedGraphNode newNode=new UndirectedGraphNode(node.label);
            copied.put(node,newNode);
            if(node.neighbors.size()>0)
            {
                for(UndirectedGraphNode aNeighbor:node.neighbors)
                {
                    UndirectedGraphNode clonedNeighbor=dfs(aNeighbor);
                        newNode.neighbors.add(clonedNeighbor);
                }
            }
            return newNode;
        }
        
        
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node==null)
                return null;
            else
            {
                copied=new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
                return dfs(node);
            }
        }
    }

Log in to reply
 

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