133. 克隆图

题目链接：https://leetcode.cn/problems/clone-graph/?envType=study-plan-v2&envId=2024-spring-sprint-100


又一次写到这个题目，思路仍然不清晰，给我的感觉是使用递归解题，但是递归具体如何，边界的处理非常不清楚。对于每个节点的neighbors 如何处理，使用一个Map，key存储某一个Node，value存储该Node对应的neighbors的List集合。但这样貌似不是很行。
既然是克隆图，那么对于原图的某个节点Node，在新克隆的节点中必然也存在对应的Node。 意识到这点后，修改上面的Map思路，将key改为原Node，value更改为原Node对应的新Node。
之后进行 dfs 搜索。具体代码参考如下：

/*
// 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) {
        Map<Node, Node> map = new HashMap<>();
        return dfs(node, map);
    }
    public Node dfs(Node root, Map<Node, Node> map){
        if(root == null){
            return root;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        Node clone = new Node(root.val, new ArrayList<>());
        map.put(root, clone);
        for(Node node : root.neighbors){
            clone.neighbors.add(dfs(node, map));
        }
        return clone;
    }
}