本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
注意：本题中文版提交的时候有 Bug，只能在英文版解答。本题来自 LeetCode：133. 克隆图[1]
题目描述
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
Example:
Input:
{"$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}
Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.
Note:
The number of nodes will be between 1 and 100.
The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
You must return the copy of the given node as a reference to the cloned graph.
广度优先遍历
题目分析
本题题意就是拷贝图，先采用广度优先遍历解答。可以分成两步：
题目解答
/*
// Definition for a Node.
class Node {
public int val;
public ListNode neighbors;
public Node(int _val) {
val = _val;
neighbors = new ArrayListNode();
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if(node == null) {
return null;
}
// 存储老节点和新节点的映射关系
MapNode, Node table = new HashMap();
ListNode queue = new LinkedList();
queue.add(node);
// 先拷贝个节点
while(!queue.isEmpty()) {
Node oldNode = queue.remove(0);
// 注意：Node实际的构造函数很注释的不一致
table.put(oldNode, new Node(oldNode.val, new ArrayListNode()));
for(Node neighbor : oldNode.neighbors) {
if(!table.containsKey(neighbor)) {
queue.add(neighbor);
}
}
}
// 连接相邻节点
for(Map.EntryNode, Node entry : copyTable.entrySet()) {
Node oldNode = entry.getKey();
Node newNode = entry.getValue();
for(Node neighbor : oldNode.neighbors) {
newNode.neighbors.add(table.get(neighbor));
}
}
return table.get(node);
}
}
复杂度分析：
时间复杂度：
O(n ^ 2)，
n个节点可能会相互相邻。
空间复杂度：
O(n)，节点最多和其余
n-1个节点相邻，故队列最大长度可能为
n - 1
深度优先遍历
题目分析
先采用深度优先遍历解答。可以分成两步：
题目解答
/*
// Definition for a Node.
class Node {
public int val;
public ListNode neighbors;
public Node(int _val) {
val = _val;
neighbors = new ArrayListNode();
}
}
*/
class Solution {
public void dfs(Node node, MapNode, Node table) {
if(table.containsKey(node)) {
return;
}
// 注意：Node实际的构造函数和注释的不一致
table.put(node, new Node(node.val, new ArrayListNode()));
for(Node neighbor : node.neighbors) {
if(!table.containsKey(neighbor)) {
dfs(neighbor, table);
}
}
}
public Node cloneGraph(Node node) {
if(node == null) {
return null;
}
// 映射关系
MapNode, Node table = new HashMap();
// 深度遍历
dfs(node, table);
// 连接相邻节点
for(Map.EntryNode, Node entry : table.entrySet()) {
Node oldNode = entry.getKey();
Node newNode = entry.getValue();
for(Node neighbor : oldNode.neighbors) {
newNode.neighbors.add(table.get(neighbor));
}
}
return table.get(node);
}
}
复杂度分析：
时间复杂度：
O(n ^ 2)，
n个节点可能会相互相邻。
空间复杂度：
O(n)，节点可能为首尾相连的链表
优化版深度遍历
题目分析
深度遍历可以直接在遍历的时候，就将响铃节点链表设置好。
题目解答
/*
// Definition for a Node.
class Node {
public int val;
public ListNode neighbors;
public Node(int _val) {
val = _val;
neighbors = new ArrayListNode();
}
}
*/
class Solution {
public Node dfs(Node node, MapNode, Node table) {
if(table.containsKey(node)) {
return table.get(node);
}
Node newNode = new Node(node.val, new ArrayListNode());
// 注意：Node实际的构造函数和注释的不一致
table.put(node, newNode);
for(Node neighbor : node.neighbors) {
newNode.neighbors.add(dfs(neighbor, table));
}
return newNode;
}
public Node cloneGraph(Node node) {
if(node == null) {
return null;
}
// 深度遍历
return dfs(node, new HashMap());
}
}
复杂度分析：
时间复杂度：
O(n ^ 2)，
n个节点可能会相互相邻。
空间复杂度：
O(n)，节点可能为首尾相连的链表
参考资料
原文始发于微信公众号（xiaogan的技术博客）：
