133.克隆图 (Medium)*

题目描述*

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

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

提示*

节点数介于 1 到 100 之间。每个节点值都是唯一的。

无向图是一个简单图，这意味着图中没有重复的边，也没有自环。

由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。

图是连通图，你可以从给定节点访问到所有节点。

代码*

dfs，用 unordered_map 保存已生成结点。

dfs

/*
// 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:
    Node* cloneGraph(Node* node) {
        if(node == nullptr) {
            return nullptr;
        }
        unordered_map<Node*, Node*> nodeMap;
        return dfs(node, nodeMap);
    }
    Node* dfs(Node* node, unordered_map<Node*, Node*>& nodeMap) {
        if(nodeMap.count(node)) {
            return nodeMap[node];
        }
        Node *cur = new Node(node->val);
        nodeMap[node] = cur;
        for(int i = 0; i < node->neighbors.size(); i++) {
            if(node->neighbors[i] != nullptr) {
                cur->neighbors.push_back(dfs(node->neighbors[i], nodeMap));
            }
        }
        return cur;
    }
};

最后更新: July 23, 2022