DFS, hashmap记录已经复制过的node
/** * 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) { HashMap<Integer, UndirectedGraphNode> copied = new HashMap<Integer, UndirectedGraphNode>(); UndirectedGraphNode root = cloneGraphHelper(node, copied); return root; } private UndirectedGraphNode cloneGraphHelper(UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> copied) { if (node == null) { return null; } if (copied.get(node.label) != null) { return copied.get(node.label); } UndirectedGraphNode root = new UndirectedGraphNode(node.label); copied.put(root.label, root); for (UndirectedGraphNode n : node.neighbors) { root.neighbors.add(cloneGraphHelper(n, copied)); } return root; } }
原文:http://www.cnblogs.com/ilovenaomi/p/5065452.html