图与链表的深拷贝

图与链表的深拷贝

都用到了unordered_map：原节点->拷贝节点，在遍历的过程中完成复制。

图：leetcode 133.克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
public int val;
public List neighbors;
}

DFS

维护一个unordered_map<Node*, Node*> vis，如果已经拷贝过该节点，直接返回拷贝节点；如果未拷贝过，就创建该节点的副本，遍历该节点的邻居，给副本的邻接链表添加邻居对应的副本。

/*
// 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:
    unordered_map<Node*, Node*> vis;
    Node* cloneGraph(Node* node) {
        if(!node) return node;
        if(vis.count(node)) return vis[node];
        auto cp = new Node(node->val);
        vis[node] = cp;
        for(auto x : node->neighbors)
        {
            vis[node]->neighbors.push_back(cloneGraph(x));
        }
        return cp;
    }
};

BFS

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node) return node;
        queue<Node*> Q;
        unordered_map<Node*, Node*> mp;
        mp[node] = new Node(node->val);
        Q.push(node);
        while(Q.size())
        {
            auto t = Q.front();
            Q.pop();
            for(auto x : t->neighbors)
            {
                if(mp.count(x))
                {
                    mp[t]->neighbors.push_back(mp[x]);
                    continue;
                }
                Q.push(x);
                mp[x] = new Node(x->val);
                mp[t]->neighbors.push_back(mp[x]);
            }
        }
        return mp[node];
    }
};

链表：leetcode 138. 复制带随机指针的链表

维护一个unordered_map<Node*, Node*> mp，如果该节点的拷贝已经存在，就返回它的拷贝节点，否则创建拷贝节点更新mp，紧接着设置拷贝节点的next和random。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> mp;
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        if(mp.count(head)) return mp[head];
        auto cp = new Node(head->val);
        mp[head] = cp;
        mp[head]->next = copyRandomList(head->next);
        mp[head]->random = copyRandomList(head->random);
        return mp[head];
    }
};