What is wrong with this recursive solution (time limit exceed)?


  • 0
    L
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node ==NULL) return node;
        UndirectedGraphNode* head = new UndirectedGraphNode(node -> label); 
        for (auto x : node -> neighbors) {
            if (x->label != head->label)
            (head->neighbors).push_back(cloneGraph(x));
        }
        return head;
    

    I think most solutions use unordered_map and check if the node has been visited (it connects to itself) by checking if the node is already in the unordered map. I am just confused why this is different from "x->label != head->label"? Or there may be other problems with this implementation. Thanks for your help!


  • 0
    Z

    "x->label != head->label" is not enough for detecting a loop that has 3 and more nodes. You will enter an infinite loop in such situation.


Log in to reply
 

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