題目描述:對一個無向連通圖進行深拷貝,每個節點包含值與相鄰節點列表。
解題思路:用 DFS(或 BFS)搭配雜湊表實現。雜湊表映射「原節點 → 複製節點」,用於追蹤已複製的節點以防止無限迴圈。對每個節點:若已在雜湊表中,直接回傳複製版;否則建立新節點、加入雜湊表,然後遞迴複製所有鄰居並加入新節點的鄰居列表。
時間複雜度:O(V + E) — 每個節點和邊各訪問一次。
空間複雜度:O(V) — 雜湊表與遞迴棧,最壞情況下深度為 V。
1. If node is null: return null 2. If node already in visited map: return visited[node] 3. Create clone = new Node(node.val) 4. visited[node] = clone 5. For each neighbor in node.neighbors: clone.neighbors.push_back(cloneGraph(neighbor)) 6. Return clone
BFS O(N+E) 時間,O(N) 空間:用隊列替換遞迴棧 — 邏輯相同但使用 BFS 而非 DFS。
迭代 DFS O(N+E) 時間,O(N) 空間:用顯式堆疊模擬遞迴 — 同複雜度但避免系統遞迴深度限制。