给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。
示例：
输入:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
解释:
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
提示:
-
节点数介于 1 到 100 之间。
-
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
-
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
-
必须将给定节点的拷贝作为对克隆图的引用返回。
节点Node的结构
1class Node {
2 public int val;
3 public List<Node> neighbors;
4
5 public Node() {
6 }
7
8 public Node(int _val, List<Node> _neighbors) {
9 val = _val;
10 neighbors = _neighbors;
11 }
12}
答案：
1public HashMap<Integer, Node> map = new HashMap<>();
2
3public Node cloneGraph(Node node) {
4 return clone(node);
5}
6
7public Node clone(Node node) {
8 if (node == null)
9 return null;
10 if (map.containsKey(node.val))
11 return map.get(node.val);
12 Node newNode = new Node(node.val, new ArrayList<Node>());
13 map.put(newNode.val, newNode);
14 for (Node neighbor : node.neighbors)
15 newNode.neighbors.add(clone(neighbor));
16 return newNode;
17}
代码比较简单，下面我们再来看一个非递归的解法
1private Map<Node, Node> map = new HashMap<Node, Node>();
2
3public Node cloneGraph(Node node) {
4 if (node == null) return null;
5 Queue<Node> q = new LinkedList<Node>();
6 q.add(node);
7 Node copy = new Node(node.val, new ArrayList<Node>());
8 map.put(node, copy);
9 while (!q.isEmpty()) {
10 Node cur = q.poll();
11 for (Node neigh : cur.neighbors) {
12 if (map.containsKey(neigh))
13 map.get(cur).neighbors.add(map.get(neigh));
14 else {
15 Node neighCopy = new Node(neigh.val, new ArrayList<Node>());
16 map.put(neigh, neighCopy);
17 map.get(cur).neighbors.add(neighCopy);
18 q.add(neigh);
19 }
20 }
21 }
22 return copy;
23}