请分别用深度优先思想和广度优先思想实现一个拷贝函数？

Question

实现深度优先思想（DFS）和广度优先思想（BFS）的深拷贝函数，分别模仿这两种遍历方式，处理对象和数组等复杂结构的数据复制。深拷贝函数会递归地复制对象中的所有属性或数组中的所有元素，确保修改副本不会影响原对象。

1. 深度优先（DFS）实现深拷贝

深度优先拷贝首先递归地深入到对象或数组的最深处，然后逐步回溯，构建整个副本。

function deepCopyDFS(obj, visited = new Map()) {
    // 如果是基础类型，直接返回
    if (obj === null || typeof obj !== 'object') {
        return obj;
    }

    // 如果已经拷贝过这个对象，直接返回防止循环引用
    if (visited.has(obj)) {
        return visited.get(obj);
    }

    // 创建新对象或数组
    const copy = Array.isArray(obj) ? [] : {};

    // 存储拷贝的引用，防止循环引用
    visited.set(obj, copy);

    // 遍历属性或数组元素，递归深拷贝
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            copy[key] = deepCopyDFS(obj[key], visited);
        }
    }

    return copy;
}

// 测试
const original = {
    a: 1,
    b: { c: 2, d: [3, 4] },
    e: function() { console.log('hello'); }
};

const copied = deepCopyDFS(original);
console.log(copied); // 输出与 original 结构相同的深拷贝对象

2. 广度优先（BFS）实现深拷贝

广度优先拷贝按层次逐步展开对象或数组，利用队列管理当前要处理的节点。逐层复制数据结构。

function deepCopyBFS(obj) {
    // 如果是基础类型，直接返回
    if (obj === null || typeof obj !== 'object') {
        return obj;
    }

    const visited = new Map(); // 存储已经访问过的对象，防止循环引用
    const queue = [{ source: obj, copy: Array.isArray(obj) ? [] : {} }];
    visited.set(obj, queue[0].copy);

    while (queue.length > 0) {
        const { source, copy } = queue.shift();

        for (let key in source) {
            if (source.hasOwnProperty(key)) {
                const value = source[key];

                if (value !== null && typeof value === 'object') {
                    if (visited.has(value)) {
                        copy[key] = visited.get(value); // 避免循环引用
                    } else {
                        const newCopy = Array.isArray(value) ? [] : {};
                        copy[key] = newCopy;
                        visited.set(value, newCopy);
                        queue.push({ source: value, copy: newCopy });
                    }
                } else {
                    copy[key] = value; // 处理基本类型
                }
            }
        }
    }

    return queue[0].copy; // 返回拷贝的根节点
}

// 测试
const originalBFS = {
    a: 1,
    b: { c: 2, d: [3, 4] },
    e: function() { console.log('hello'); }
};

const copiedBFS = deepCopyBFS(originalBFS);
console.log(copiedBFS); // 输出与 originalBFS 结构相同的深拷贝对象

3. 深度优先（DFS）和广度优先（BFS）拷贝的对比

• DFS ：递归深入到最深处，然后逐步回溯，适合处理嵌套层次较深的结构。但如果嵌套层次太深，可能会导致栈溢出，递归需要注意性能优化。
• BFS ：逐层复制结构，利用队列管理，适合层次结构较广但嵌套较浅的情况。可以避免栈溢出问题，但需要额外的队列来存储待处理节点。

选择哪种拷贝方式可以根据具体数据结构的特征和性能要求进行权衡。如果嵌套层次较深且担心递归过深，BFS 可能更安全；但如果数据结构较简单，DFS 通常会更直观和简洁。