克隆图

Leetcode题目链接

描述

详见中文题目链接。

解答

/*
// 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 {
private:
    unordered_map<Node*, Node*> visited;
public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr) return node;

        // If the node has already been accessed, the corresponding clone is returned directly from the hash table
        if (visited.count(node)) return visited[node];

        // Clone the node, noting that for deep copy we will not clone the list of its neighbors
        Node* clone = new Node(node->val);
        visited[node] = clone;

        // Iterate through the neighbors of this node and update the neighbor list of the cloned node
        for (auto& neighbor : node->neighbors) {
            clone->neighbors.emplace_back(cloneGraph(neighbor));
        }
        return clone;
    }
};