[leetcode] Clone Graph

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); mapClone(node, cloneNodes); UndirectedGraphNode[] allNodes = cloneNodes.keySet() .toArray(new UndirectedGraphNode[cloneNodes.size()]); for (int i = 0; i < allNodes.length; i++){ UndirectedGraphNode copyNode = cloneNodes.get(allNodes[i]); List<UndirectedGraphNode> neighbors = allNodes[i].neighbors; for (int j = 0; j < neighbors.size(); j++){ copyNode.neighbors.add(cloneNodes.get(neighbors.get(j))); } } return cloneNodes.get(node); } public void mapClone(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes){ if (cloneNodes.containsKey(node)) return; cloneNodes.put(node, new UndirectedGraphNode(node.label)); List<UndirectedGraphNode> neighbors = node.neighbors; for (int i = 0; i < neighbors.size(); i++){ mapClone(neighbors.get(i), cloneNodes); } } }