133. Clone Graph

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

image.png

（图片来源https://leetcode-cn.com/problems/clone-graph/

）

日期	是否一次通过	comment
2020-03-17	0

---

递归

public Node cloneGraph(Node node) {
        if(node == null) {
            return node;
        }

        Map<Node, Node> nodeMap = new HashMap<>();  // 存 {旧节点：新节点}

        return clone(node, nodeMap);
    }


    private Node clone(Node node, Map<Node, Node> nodeMap) {
        if(node == null) {
            return null;
        }

        if(nodeMap.containsKey(node)) {
            return nodeMap.get(node);
        }

        Node newNode = new Node(node.val, new ArrayList<>());
        nodeMap.put(node, newNode);

        for (Node neighbor : node.neighbors) {
            newNode.neighbors.add(clone(neighbor, nodeMap));
        }


        return newNode;
    }