Untitled
plain_text
16 days ago
1.2 kB
1
Indexable
Never
/* // Definition for a Node. class Node { public: int val; vector<Node*> neighbors; Node() { val = 0; neighbors = vector<Node*>(); } Node(int _val) { val = _val; neighbors = vector<Node*>(); } Node(int _val, vector<Node*> _neighbors) { val = _val; neighbors = _neighbors; } }; */ class Solution { public: Node* dfs(Node* node,unordered_map<Node*,Node*>&ot){ Node* clone =new Node(node->val); vector<Node*> cneighbor; ot[node]=clone; for(Node* nbr:node->neighbors){ if(ot.find(nbr)!=ot.end()){ //clone exists cneighbor.push_back(ot[nbr]); }else{ cneighbor.push_back(dfs(nbr,ot)); //calls recursion on the not yet visited neighboring node } } clone->neighbors=cneighbor; return clone; } Node* cloneGraph(Node* node) { unordered_map<Node*,Node*> ot; if(node==NULL) return NULL; if(node->neighbors.size()==0){ Node* clone=new Node(node->val); return clone; } return dfs(node,ot); } };