博文中会简要介绍Leetcode P0133题目分析及解题思路。
“Clone Graph”这道题是一道比较基础的深度优先搜索，运用递归回溯的思想，这道题的核心在于记忆化，即存储每个已经访问过的结点，通过将其映射到其克隆副本上，完成对环的克隆。
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.
class Node { public int val; public List<Node> neighbors; }
以下是Java的题解代码实现。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null)
return null;
return this.clone(node, new HashMap<>());
}
private Node clone(Node curr, Map<Node, Node> old2NewMap) {
Node cloned = new Node(curr.val);
old2NewMap.put(curr, cloned);
for (Node neighbor: curr.neighbors) {
if (old2NewMap.containsKey(neighbor)) {
cloned.neighbors.add(old2NewMap.get(neighbor));
}
else {
cloned.neighbors.add(this.clone(neighbor, old2NewMap));
}
}
return cloned;
}
}
以下是C++的题解代码实现。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* cloneGraph(Node* node) {
if (!node)
return NULL;
unordered_map<Node*, Node*> old2new;
return this->_Clone(node, old2new);
}
private:
Node* _Clone(Node *curr, unordered_map<Node*, Node*> &old2new) {
Node *cloned = new Node(curr->val);
old2new[curr] = cloned;
for (Node *neighbor: curr->neighbors) {
if (old2new.count(neighbor)) {
cloned->neighbors.push_back(old2new[neighbor]);
}
else {
cloned->neighbors.push_back(this->_Clone(neighbor, old2new));
}
}
return cloned;
}
};