js 中去掉树结构重复的 子结构数据

在JavaScript中，如果你有一个树形数据结构，并希望移除其中的重复子结构，你可以通过深度优先搜索(DFS)或广度优先搜索(BFS)结合哈希集合(set)来实现。这里是一个简单的递归方法示例：

function removeDuplicateSubtrees(root) {
    const hash = new Map();

    function getTreeHash(node) {
        if (!node) return '#';
        let str = node.val + '#' + getTreeHash(node.left) + getTreeHash(node.right);
        return hash.has(str) ? hash.get(str) : (hash.set(str, node), str);
    }

    root.hash = getTreeHash(root);

    return root;
}

// 示例：
let tree1 = {val: 1, left: {val: 2}, right: {val: 2}};
let tree2 = {val: 1, left: {val: 3}, right: null};

let result = removeDuplicateSubtrees(tree1); // 结果是去除了重复子结构后的tree1

这个函数首先创建了一个`Map`用于存储已经遇到过的子结构的哈希值。然后定义一个内部辅助函数`getTreeHash`，它将节点值、左子树和右子树的哈希连接起来作为新的键。如果键已存在，说明找到了重复的子结构，直接返回对应的值；否则添加到哈希集中并返回当前节点。

最后，我们给`root`节点设置一个`hash`属性，以便后续比较。