前言

在上一篇我们学习了用js解决二叉树的序列化和反序列化的问题，其实序列化的过程就是考察二叉树遍历的过程，反序列化的过程就是考察了二叉树的构造过程，结合了前几章的知识。本篇文章深入学习二叉树后序的妙用，带你了解以下题目：

Leetcode
652.寻找重复的子树

寻找重复的子树

这道题实际上就是找子树的问题，看下图

首先节点4可以作为一颗子树，二叉树中有多个节点4

类似的还存在两颗以2为根的重复子树

那么我们返回的list就应该有两个treenode，2和4

具体这道题要怎么做呢？先思考对于一个节点他应该做什么？

我们拿这个2节点作为例子，他是不是重复的子树，是不是就要先知道自己是一颗怎么样的子树，再去找别的子树进行对比？

那么我们解题的关键就来了：

先知道自己长什么样
去看看别人有没有和自己一样的

那么对于第一个问题，根据本文你可以知道我们要用后序遍历的操作去做，其实前序中序都可以，只不过后序在这个阶段看的东西更明显，怎么知道自己是谁呢？其实就是自身加左右子树

const postoreder = (n)=>{
  if(!n)return null;
  let left = postoreder(n.left);
  let right = postoreder(n.right);
  return `${left},${right},${n.val}`;
  //n 就是一颗树了
}

这样不就能知道自己是谁了吗？一看这个问题，你就会发现，和之前的序列化二叉树及其相似，其实知道自己是谁的这个过程，就是经历了一次序列化。

那么现在怎么解决找同伴的问题呢？其实很简单，我们运用js的set或者map，考量这两个api用哪个的时候，我们先看我们需要什么？我们需要记录出现次数超过一次的子树，也就是记录子树+子树出现次数，所以用map更好。完整代码如下：

var findDuplicateSubtrees = function(root) {
    //定义map集合和存放的数组
    const map = new Map(),res = [];
    
    const tranverse = root =>{
        if(!root)return '#';
        const left = tranverse(root.left);
        const right = tranverse(root.right);
        const str = `${left},${right},${root.val}`;
        const count = map.get(str);
        if(count===1){
            //等于1就存放子树
            res.push(root);
        }
        map.set(str,(count||0)+1);
        return str;
    }

    tranverse(root);
    return res;
};