Accepted recursive depth first search solution

  • 19
    class Solution {
    	UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) 
    		// initialize marks
    		map<int, UndirectedGraphNode*> marks;
    		if (node) return dfs(node, marks);
    		else return NULL;
    	UndirectedGraphNode * dfs(UndirectedGraphNode *node, map<int, UndirectedGraphNode*> & marks)
    		// create new node and search its all neighbors
    		UndirectedGraphNode *p;
    		p = new UndirectedGraphNode(node->label);
    		marks[p->label] = p;
    		// loop all neighbors
    		for(UndirectedGraphNode* n : node->neighbors)
    			// hook already created and searched node
    			if(marks.count(n->label) > 0)
    		return p;

  • 0
    This post is deleted!

  • 0

    who can tell me the difference between the following statements:

    1. (p->neighbors).push_back(marks[n->label]);
    2. (p->neighbors).push_back(n);
      why the second is wrong ?

  • 0

    I figure it out : marks[n->label] is the copy of n, they are not the same address.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.