力扣 133 克隆图

题意：给定一个graph，生成一个deep copy的graph

思路：递归遍历每一个graph的node，具体见注释

思想：递归

复杂度：时间O（n²)，空间O(n)

class Solution {
    // key是已经遍历过的节点，value是遍历过的节点创建的新节点
    HashMap<Node, Node> map = new HashMap();
    public Node cloneGraph(Node node) {
        return build(node);
    }
    Node build(Node node) {
        // 节点为空返回null
        if(node == null)
            return null;
        // 节点遍历过，返回对应的创建的节点
        if(map.containsKey(node))
            return map.get(node);
        // 根据新遍历的节点创建新节点
        Node temp = new Node(node.val);
        map.put(node, temp);
        List<Node> list = new ArrayList();
        // 生成新节点的neighbors
        if(node.neighbors.size() > 0) {
            for(Node n: node.neighbors) {
                list.add(build(n));
            }
        }
        temp.neighbors = list;
        return temp;
    }
}