C++ Iterative DFS


  • 0
    1

    Not as efficient as the recursive one.

    class Solution {
    public:
        map<UndirectedGraphNode *,UndirectedGraphNode *>visited;
        UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
            if(!node) return NULL;
            UndirectedGraphNode *root=new UndirectedGraphNode(node->label);
            stack<UndirectedGraphNode *> s;
            visited[node]=root;
            while (1){
                while((node->neighbors).size()){
                    UndirectedGraphNode *tmp=*(node->neighbors).begin();
                    (node->neighbors).erase((node->neighbors).begin());
                    s.push(node);
                    if(!visited[tmp])
                        visited[tmp]=cloneGraph(tmp);
                    (root->neighbors).push_back(visited[tmp]);
                    node=tmp;
                }
                if(s.empty()) return root;
                node=s.top();
                s.pop();
            }
            return root;
        }
    };
    

Log in to reply
 

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