🤣133 clone graph

https://leetcode.com/problems/clone-graph/

见注释 感觉以前也错过

/*
// 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) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        return clone(node, map);
    }
    private Node clone(Node node, Map<Node, Node> map) {
        if (map.containsKey(node)) {
            return map.get(node);
        }
        Node newNode = new Node(node.val);
        // put要放在clone neighbor的前面！
        map.put(node, newNode);
        for (int i = 0; i < node.neighbors.size(); i++) {
            newNode.neighbors.add(clone(node.neighbors.get(i), map));
        }
        return newNode;
    }
}