題目
#

題目簡述
#

給一個無向連通圖，請返回該圖的深拷貝（Deep Copy）。
圖中的每個節點都包含一個值（int）和一個鄰居節點列表（List[Node]）。

範例
#

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 圖中有 4 個節點。
第 1 個節點（值 = 1）的鄰居是第 2 個節點（值 = 2）和第 4 個節點（值 = 4）。
第 2 個節點（值 = 2）的鄰居是第 1 個節點（值 = 1）和第 3 個節點（值 = 3）。
第 3 個節點（值 = 3）的鄰居是第 2 個節點（值 = 2）和第 4 個節點（值 = 4）。
第 4 個節點（值 = 4）的鄰居是第 1 個節點（值 = 1）和第 3 個節點（值 = 3）。

graph LR; A[1] B[2] C[3] D[4] A --- B A --- D B --- C C --- D

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: 圖中只有 1 個節點（值 = 0），且沒有鄰居節點。因此複製後的圖也包含 1 個沒有鄰居的節點。

解題思路
#

這題要求我們對一個無向圖進行深拷貝。我們可以使用遞迴的方法，通過HashMap來儲存原始節點和複製節點的對應關係，避免重複複製同一個節點，從而避免無限遞迴。

解法
#

使用 HashMap 儲存原始節點和複製節點的對應關係
如果節點已經被複製過，直接返回複製的節點
創建新的節點，複製節點值
遞迴複製所有鄰居節點
返回複製的節點

步驟
#

初始化：
- 創建 HashMap 儲存原始節點和複製節點的對應關係
遞迴複製：
- 檢查節點是否已經被複製過
- 如果已複製，直接返回複製的節點
- 如果未複製，創建新的節點並複製節點值
複製鄰居：
- 遞迴複製所有鄰居節點
- 將複製的鄰居節點加入新節點的鄰居列表
返回結果：
- 返回複製的節點

例子說明
#

adjList = [[2,4],[1,3],[2,4],[1,3]]

graph LR; A[1] B[2] C[3] D[4] A --- B A --- D B --- C C --- D

步驟	當前節點	節點值	是否已複製	鄰居節點	複製結果
初始化	-	-	-	-	開始複製
第 1 步	節點 1	1	否	[2,4]	創建新節點 `1'`
第 2 步	節點 2	2	否	[1,3]	創建新節點 `2'`
第 3 步	節點 3	3	否	[2,4]	創建新節點 `3'`
第 4 步	節點 4	4	否	[1,3]	創建新節點 `4'`

最終結果： [[2,4],[1,3],[2,4],[1,3]]

複製過程說明：

步驟 1：複製節點 1，鄰居為節點 2 和 4
步驟 2：複製節點 2，鄰居為節點 1 和 3
步驟 3：複製節點 3，鄰居為節點 2 和 4
步驟 4：複製節點 4，鄰居為節點 1 和 3

完整程式碼
#

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 {
    // 儲存原始節點和複製節點的對應關係，避免重複複製
    Map<Node,Node> map = new HashMap<>();

    public Node cloneGraph(Node node) {
        // 邊界條件：如果節點為空，返回 null
        if(node == null) {
            return null;
        }

        // 如果節點已經被複製過，直接返回複製的節點
        if(map.containsKey(node)){
            return map.get(node);
        }

        // 創建新的節點，複製節點值
        Node copy = new Node(node.val);
        // 將原始節點和複製節點的對應關係存入 HashMap
        map.put(node,copy);

        // 遞迴複製所有鄰居節點
        for(Node neighbor : node.neighbors){
            copy.neighbors.add(cloneGraph(neighbor));
        }
        
        return copy;
    }
}