[leetcode]133. Clone Graph 克隆图

 

题目

给定一个无向图的节点，克隆能克隆的一切

 

思路

1--2 | 3--5

以上图为例，

node    neighbor

  1         2， 3

  2         1 

  3         1， 5

  5         3

首先从1开始,  将（node，newNode）put到HashMap中

node        newNode

  1                1 

然后遍历该node的所有neighbor

node    neighbor

  1         2， 3

此时遍历到2 

将（node，newNode）put到HashMap中

node        newNode

  1                1 -- 2  // newNode.neighbors.add(clone)

  2               2 

 

代码

1 public class Solution { 2 3 Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>(); 4 5 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 6 if (node == null) { 7 return null; 8 } 9 10 //DFS 11 if (map.containsKey(node)) { 12 return map.get(node); 13 } 14 15 UndirectedGraphNode newNode = new UndirectedGraphNode(node.label); 16 map.put(node, newNode); 17 for (UndirectedGraphNode nei : node.neighbors) { 18 UndirectedGraphNode clone = cloneGraph(nei); 19 newNode.neighbors.add(clone); 20 } 21 return newNode; 22 } 23 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/10014918.html