【leetcode】133.克隆图.md

==题目描述==

==题目思路==

• 拷贝所有节点
• 拷贝所有的边

==个人题解==

1. 遍历所有的节点
2. 拷贝所有节点存储起来
3. 将拷贝的节点根据原图的方式进行链接

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {
    // 1.   遍历所有的节点
    // 2.   拷贝所有节点存储起来
    // 3.   将拷贝的节点根据原图的方式进行链接
    if (!node) return;
    // 用map主要是为了建立映射关系.n和nCopy 还有neighbor之间
    const visited = new Map();
    // 深度遍历
    const dfs = (n) => {
        const nCopy = new Node(n.val);
        visited.set(n, nCopy);
        // 这里判[],是为了不影响程序继续执行.
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)) {
                dfs(ne);
            }
            //当前遍历的是n.neighbors, 加入到nCopy数组中.
            // 这里需要注意,加入的是nCopy
            nCopy.neighbors.push(visited.get(ne));
        });
    };
    dfs(node);
    return visited.get(node);
};

==总结优化==

下面是广度遍历

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function (node) {

    if (!node) return;
    const visited = new Map();
    visited.set(node, new Node(node.val))
    const q = [node];
    while (q.length) {
        const n = q.shift();
        
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)) {
                q.push(ne);
                visited.set(ne, new Node(ne.val));
            }
            visited.get(n).neighbors.push(visited.get(ne));
        })
    }
    return visited.get(node);
};

==时间复杂度（time complexity）==

O(n)

==空间复杂度（space complexity）==

O(n) map数据结构

• 为什么不看递归的空间复杂度呢?

  • 如果两个结构前后排列,就返回更大的那个.