克隆图

LeetCode-133

• 使用一个map来存储已经遍历的结点，这个存起来的结点必须是新new的才符合题意

/*
// 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 {
    boolean[] flag;
    HashMap<Integer,Node>hashmap=new HashMap<>();
    public Node dfs(Node node){
        Node nows=new Node();
        nows.val=node.val;
        hashmap.put(node.val,nows);
        List<Node> list=node.neighbors;
        ArrayList<Node> newlist=new ArrayList<>();
        for(Node temp:list){
            Node now;
            if(!flag[temp.val]){
                flag[temp.val]=true;
                now=dfs(temp);
            }else {
                now=hashmap.get(temp.val);
            }
            newlist.add(now);
        }
        nows.neighbors=newlist;
        return nows;
    }
    public Node cloneGraph(Node node) {
        flag=new boolean[110];
        Arrays.fill(flag,false);
        if(node==null)
            return null;
        flag[node.val]=true;
        return dfs(node);
    }
}