[LeetCode]Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Nodes are labeled uniquely.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

   Visually, the graph looks like the following:

          1
         / \
        /   \
       0 --- 2
            / \
            \_/

   
   

   利用递归深搜，同时用一个map存储已经 new 过的node，如果已经new 过则直接返回存在map里的节点

   /**
    * Definition for undirected graph.
    * class UndirectedGraphNode {
    *     int label;
    *     List
       
         neighbors;
    *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList
        
         (); } * }; */ public class Solution { Map
         
           map = new HashMap<>(); public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) return null; if(map.containsKey(node)){ return map.get(node); } UndirectedGraphNode ug = new UndirectedGraphNode(node.label); map.put(node, ug); for (int i = 0; i < node.neighbors.size(); i++) { ug.neighbors.add(cloneGraph(node.neighbors.get(i))); } return ug; } }