寻找重复子树

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

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

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

示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-duplicate-subtrees

如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？

你需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？

2、以其他节点为根的子树都长啥样？

那我们一个一个来解决，先来思考，我如何才能知道以自己为根的二叉树长啥样？

其实看到这个问题，就可以判断本题要使用「后序遍历」框架来解决：

String traverse(TreeNode root) {
    // 对于空节点，可以用一个特殊字符表示
    if (root == null) {
        return "#";
    }
    // 将左右子树序列化成字符串
    String left = traverse(root.left);
    String right = traverse(root.right);
    /* 后序遍历代码位置 */
    // 左右子树加上自己，就是以自己为根的二叉树序列化结果
    String subTree = left + "," + right + "," + root.val;
    return subTree;
}

将二叉树序列化可解决第一个问题

借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，不就可以知道有没有其他节点的子树和自己重复了么？

初步思路可以使用HashMap记录子树，注意要处理出现多次的重复子树

总体实现javascript代码：

/**
 * 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) {
    let map=new Map();
    let res=[];
    var traverse = function(root){//后序遍历将二叉树序列化，将每个结点形成的树存进map中
        if(!root) return '#';
        let leftnode=traverse(root.left);
        let rightnode=traverse(root.right);
        let subTree=leftnode + ','+rightnode+','+root.val;//判断每个root结点对应的序列化
        if(!map.has(subTree)) map.set(subTree,1);//第一次
        let count=map.get(subTree);//获取出现的次数
        if(count===2) {//确保多次重复的root只加入结果集一次
            res.push(root);
        }
        map.set(subTree,count+1);//记录出现的次数
        return subTree;
    }
    traverse(root);
    return res;
};

还可以用深度遍历+二叉树序列化实现

参考链接：

https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ