广度优先克隆树

在 JavaScript 中，可以使用广度优先搜索（BFS）来实现树的深拷贝。下面是一个实现的示例：

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    
    addChild(child) {
        this.children.push(child);
    }
}
function deepCopyTree(root) {
    if (!root) {
        return null; // 如果根节点为空，返回 null
    }
    // 创建一个队列用于广度优先遍历
    const queue = [];
    const clonedRoot = new TreeNode(root.value); // 复制根节点
    queue.push({ original: root, clone: clonedRoot }); // 将原始节点和克隆节点放入队列
    while (queue.length > 0) {
        const { original, clone } = queue.shift(); // 弹出队列中的第一个元素
        // 遍历当前节点的子节点
        for (const child of original.children) {
            const clonedChild = new TreeNode(child.value); // 复制子节点
            clone.children.push(clonedChild); // 将复制的子节点添加到克隆节点的子节点中
            queue.push({ original: child, clone: clonedChild }); // 将子节点的原始和克隆放入队列
        }
    }
    return clonedRoot; // 返回深拷贝的树的根节点
}
// 示例用法
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const child3 = new TreeNode(4);
root.addChild(child1);
root.addChild(child2);
child1.addChild(child3);
const clonedTree = deepCopyTree(root);
// 打印结果以验证深拷贝
console.log(clonedTree); // 输出克隆的树结构