652. 寻找重复的子树

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1]
输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function (root) {
    // 记录所有子树以及出现的次数
    const memo = new Map();
    const res = [];
    const traverse = (node) => {
        // 对于空节点，可以用一个特殊字符表示
        if (!node) {
            return "#";
        }
        // 将左右子树序列化成字符串，左右子树加上自己，就是以自己为根的二叉树序列化结果
        const key = node.val + "," + traverse(node.left) + traverse(node.right);
        let value = memo.get(key) || 0;
        // 多次重复也只会被加入结果集一次
        if (value === 1) {
            // 有人和我重复，把自己加入结果列表
            res.unshift(node);
        }
        // 给子树对应的出现次数加一
        memo.set(key, value + 1);
        return key;
    };
    traverse(root);
    return res
};