133. Clone Graph

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

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

// Definition for a Node.
// class Node {
//     public int val;
//     public List<Node> neighbors;

//     public Node() {
//     }

//     public Node(int _val, List<Node> _neighbors) {
//         val = _val;
//         neighbors = _neighbors;
//     }
// };

/**
 * DFS - Recursive
 *
 * Time Complexity: O(V + E)
 *
 * Space Complexity: O(V).
 *
 * V = Number of nodes. E = Number of edges in the graph.
 */
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();

        return cloneGraphHelper(node, map);
    }

    private Node cloneGraphHelper(Node node, Map<Node, Node> map) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }

        Node copy = new Node(node.val, new ArrayList<>());
        map.put(node, copy);

        for (Node n : node.neighbors) {
            copy.neighbors.add(cloneGraphHelper(n, map));
        }

        return copy;
    }
}

/**
 * BFS - Iterative
 *
 * Time Complexity: O(V + E)
 *
 * Space Complexity: O(V).
 *
 * V = Number of nodes. E = Number of edges in the graph.
 */
class Solution2 {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        Node clone = new Node(node.val, new ArrayList<>());

        map.put(node, clone);
        queue.offer(node);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            Node copy = map.get(cur);

            for (Node n : cur.neighbors) {
                if (map.containsKey(n)) {
                    copy.neighbors.add(map.get(n));
                } else {
                    Node nCopy = new Node(n.val, new ArrayList<>());
                    map.put(n, nCopy);
                    copy.neighbors.add(nCopy);
                    queue.offer(n);
                }
            }
        }

        return clone;
    }
}