C++ recursive solution


  • 2
    R

    The thought is to use hashmap to store the 1-to-1 relationship between the orginal node and the copied node. When processing the neighbors of a copied node, check the hashmap to see if the neighbor has already been created.

    class Solution {
    public:
        void cloneGraph_core(UndirectedGraphNode *node, UndirectedGraphNode* &res, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>& originToCopy)
        {
        	if(originToCopy[node])
        		res = originToCopy[node];
        	else
        	{
        		res = new UndirectedGraphNode(node->label);
        		originToCopy[node] = res;
        	}
        
        	int len = node->neighbors.size();
        	if(res->neighbors.empty())
        	for(int i = 0; i < len; i++)
        	{
        		res->neighbors.push_back(0);	
        		cloneGraph_core(node->neighbors[i], res->neighbors.back(), originToCopy);		
        	}
        
        }
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) 
        {
        	if(!node) return 0;
        	unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> originToCopy;
        
        	UndirectedGraphNode *res;
        	cloneGraph_core(node, res, originToCopy);       
        	return res;
        }
    
    };

  • 0
    H

    don't need the check "visited" condition? how the recursion stop if there are loops


  • 0
    R

    If a node has been visited, its "neighbors" can not be empty, which makes "res->neighbors.empty()" false, thus stops the next level recursion.


  • 0
    C

    By passing result via return value and keep the mapping inside the class, we can reduce the stack usage of the recursive solution and make the code easy to read. Here comes the code:

    class Solution {
        std::unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mapping;
        UndirectedGraphNode* copyNode(UndirectedGraphNode *node) {
            if (mapping.find(node) != mapping.end()) {
                return mapping[node];
            }
            UndirectedGraphNode* new_node = new UndirectedGraphNode(node->label);
            mapping[node] = new_node;
            for (auto i = node->neighbors.begin(); i != node->neighbors.end(); ++i) {
                new_node->neighbors.push_back(copyNode(*i));
            }
            return new_node;
        }
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            mapping.clear();
            mapping[NULL] = NULL;
            return copyNode(node);
        }
    };
    

  • 0
    T
    class Solution {
    public:
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            map<int, UndirectedGraphNode*> nodeMap;
            return cloneGraphInternal(node, nodeMap);
        }
        
    private:
        UndirectedGraphNode *cloneGraphInternal(UndirectedGraphNode *node, map<int, UndirectedGraphNode*>& m) {
            UndirectedGraphNode* h = NULL;
            if(node != NULL) {
                if(m.count(node->label) == 0) {
                    h = new UndirectedGraphNode(node->label);
                    m.insert(make_pair(h->label, h));
                } else {
                    return m[node->label];
                }
                
                for(vector<UndirectedGraphNode*>::iterator it = node->neighbors.begin(); it != node->neighbors.end(); ++it) {
                    h->neighbors.push_back(cloneGraphInternal(*it, m));
                }
            }
            return h;
        }
    };

Log in to reply
 

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