133. Clone Graph
给你一个图形,返回一个深拷贝的克隆图形,图形的点定义如下:
class Node {
public int val;
public List<Node> neighbors;
}
Example:
https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
思路:
1.用dfs遍历原Node。
2.遍历的过程复制节点并把 (node -> clone) 的关系保存到map。
3.dfs的结束条件为:map已经复制过当前node,表示已经走过。
4.遍历完返回最外层的clone node即可。
Java Code: