原题
给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 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 。
解法
思想
Hashmap维持原图节点和克隆节点的对应关系，如果给邻居节点赋值的时候不存在对应的克隆节点则获取对应的克隆节点，直到有一个节点的邻居节点的克隆节点都存在于map中。
代码
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {}
public Node(int _val,List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
//hashmap维持原图和克隆图之间节点的对应关系
Map<Node, Node> lookup;
public Node cloneGraph(Node node) {
lookup = new HashMap<>();
return dfs(node);
}
//每一次dfs操作实际上就是确保存在node节点的复制节点
private Node dfs(Node node) {
if (node == null) return null;
//存在对应的克隆节点直接返回
if (lookup.containsKey(node)) return lookup.get(node);
//先创建对应的克隆节点，邻居列表在递归返回的时候添加。
Node clone = new Node(node.val, new ArrayList<>());
lookup.put(node, clone);
for (Node n : node.neighbors)
//添加n的克隆节点
clone.neighbors.add(dfs(n));
return clone;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode133-%e5%85%8b%e9%9a%86%e5%9b%be/
