[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

代码

 public class Solution {

     Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

         if (node == null) {

             return null;

         }

         //DFS

         if (map.containsKey(node)) {

             return map.get(node);

         }

         UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

         map.put(node, newNode);

         for (UndirectedGraphNode nei : node.neighbors) {

             UndirectedGraphNode clone = cloneGraph(nei);

             newNode.neighbors.add(clone);

         }

         return newNode;

     }

 }

巴特西

[leetcode]133. Clone Graph 克隆图

最新文章

热门文章