133. 克隆图

✨核心逻辑

本题采用 深度优先搜索（DFS）+ 哈希表备忘录 的策略：

处理环与重复访问：图是可能包含环的，因此在克隆过程中，如果遇到已经被克隆过的节点（即 visited 哈希表中已经存在），直接返回之前克隆的节点，防止陷入死循环。
节点克隆：对于每一个新遇到的节点，先创建一个 val 相同，但邻居列表为空的新节点，并立即存入哈希表中。
克隆邻居（递归）：遍历原节点的 neighbors 列表，通过递归调用 cloneGraph 来深拷贝每一个邻居节点，将克隆出来的邻居节点填入当前克隆节点的 neighbors 列表中。
返回结果：递归层层返回，最终返回起始节点克隆后的深拷贝节点。

🔥代码实现（含详细变量注释）

class Solution {
    // visited：哈希表，用于记录原图中的节点 和 克隆图中对应节点 的映射关系
    // 作用：避免重复克隆，并处理图中的环引用
    private Map<Node, Node> visited = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        // 边界情况：如果传入的节点为空，直接返回 null
        if (node == null) {
            return null;
        }
        
        // 如果当前节点已经在哈希表中，说明已经被克隆过
        // 直接返回哈希表中对应的克隆节点即可
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        
        // cloneNode：为当前原节点创建一个对应的克隆节点
        // 初始化时，val 相同，邻居列表初始化为空 ArrayList
        Node cloneNode = new Node(node.val, new ArrayList<>());
        
        // 将原节点和克隆节点的映射存入哈希表（必须在递归邻居之前存入，防止递归成环）
        visited.put(node, cloneNode);
        
        // 遍历原节点的所有邻居节点
        for (Node neighbor : node.neighbors) {
            // 递归调用 cloneGraph 克隆每一个邻居节点
            // 并将克隆出来的邻居节点，添加到 cloneNode 的邻居列表中
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        
        // 返回克隆完成的当前节点
        return cloneNode;
    }
}

⏱️复杂度分析
- 时间复杂度：O(N + M)，其中 N 是图中的节点总数，M 是图中的边数。由于我们只遍历每个节点一次，并且对每条边也处理一次，因此整体时间复杂度与图的规模成正比。
- 空间复杂度：O(N)。主要消耗在于 visited 哈希表存储了 N 个节点的映射关系，以及 DFS 递归调用时系统栈的深度（最坏情况下为 N）。