Clone graph

O(n) : where n is no. of nodes Problem /* Definition for a Node. class Node { public int val; public List neighbors; public Node() { val = 0; neighbors = new ArrayList(); } public Node(int _val) { val = _val; neighbors = new ArrayList(); } public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { public Node cloneGraph(Node node) { if(node ==null) return null; Map map = new HashMap(); Node cloneNode = new Node(node.val); return dfs(node,cloneNode,map); } public Node dfs(Node a, Node b,Map map){ if(map.containsKey(a)) return map.get(a); map.put(a,b); for(Node adjNode : a.neighbors){ if(!map.containsKey(adjNode)){ Node newNode = new Node(adjNode.val); b.neighbors.add(dfs(adjNode,newNode,map)); } else{ b.neighbors.add(map.get(adjNode)); } } return b; } }

Mar 20, 2025 - 18:36

O(n) : where n is no. of nodes
Problem

/*
Definition for a Node.
class Node {
    public int val;
    public List neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList();
    }
    public Node(int _val, ArrayList _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if(node ==null) return null;
        Map<Node,Node> map = new HashMap<>();
        Node cloneNode = new Node(node.val);
        return dfs(node,cloneNode,map);
    }

    public Node dfs(Node a, Node b,Map<Node,Node> map){
        if(map.containsKey(a)) return map.get(a);
        map.put(a,b);
        for(Node adjNode : a.neighbors){
            if(!map.containsKey(adjNode)){
                Node newNode = new Node(adjNode.val);
                b.neighbors.add(dfs(adjNode,newNode,map));
            }
            else{
                b.neighbors.add(map.get(adjNode));
            } 
        }
        return b;
    }
}