如何找到二叉树中的重复子树？为什么常用子树序列化做签名？
简化版
找重复子树可以给每棵子树生成唯一签名，比如“根值 + 左子树签名 + 右子树签名”，再用哈希表统计签名出现次数。某个签名第二次出现时，就说明找到一类重复子树。
详细版
重复子树要求结构相同、节点值也相同。常用后序 DFS：
- 空节点返回特殊标记
#。 - 左右子树先生成签名。
- 当前签名为
val,leftSig,rightSig。 - 用 Map 记录签名出现次数。
- 当次数从 1 变成 2 时，把当前根加入答案，避免重复加入同一类。
后序很自然，因为当前子树签名依赖左右子树签名。注意签名必须包含空节点标记，否则不同结构可能被误判相同。
完整版教学
一、重复子树的判定包含两件事
重复子树不是只看根节点值相同，也不是只看节点数量相同。它要求结构相同，并且对应位置的节点值相同。
例如：
2 2
/ \
3 3这两棵子树节点值集合一样，但结构不同，不应该算重复。签名必须同时编码值和结构。
二、为什么后序遍历适合生成签名
当前子树的签名依赖左子树和右子树。只有先知道左右签名，才能拼出当前签名。
sig(node) = node.val + "," + sig(node.left) + "," + sig(node.right)这正是后序遍历：左、右、根。后序不是随便选的，而是由依赖关系决定的。父节点要等孩子信息都准备好。
三、为什么空节点标记不能省
如果省略空节点，结构可能混淆。比如一个节点只有左孩子，和一个节点只有右孩子，字符串可能被拼得很像。
正确签名要包含 #：
只有左孩子：1,2,#,#,#
只有右孩子：1,#,2,#,#空标记让结构边界明确。序列化树时常说“空节点也要编码”，这里原因一样。
四、为什么只在第二次出现时加入答案
如果同一种重复子树出现 4 次，答案通常只需要返回一个代表根。如果每次出现都加入，会重复输出。
逻辑是：
count[sig] += 1
if (count[sig] === 2) ans.push(node)第一次出现只是建立基准；第二次出现说明确实重复；第三次以后已经报告过这一类，不需要再加。
五、字符串签名的成本和优化
直接拼字符串容易理解，但大树上字符串总长度可能较大。可以把每种三元组 (val,leftId,rightId) 映射成整数 id，用 id 作为子树签名。
| 方式 | 优点 | 缺点 |
|---|---|---|
| 字符串签名 | 简单直观 | 字符串拼接可能较重 |
| 整数 ID | 更省空间 | 实现更复杂 |
| 哈希签名 | 快 | 要考虑碰撞 |
面试中先讲字符串版，再补充 ID 优化，会显得层次很清楚。
六、复杂度怎么分析
每个节点访问一次。若用整数 ID，时间 O(n)，空间 O(n)。若用字符串，理论上拼接和存储可能让总成本高于 O(n)，但面试基础版通常接受 O(n) 节点遍历的描述，并补充字符串成本。
记忆钩子：重复子树就是给每棵子树办“身份证”；身份证必须写上根值、左子树、右子树和空节点。
七、常见误区与追问
- 误区：只比较根节点值就能判断重复。 还要比较完整结构和所有对应节点值。
- 误区：空节点标记可以省略。 省略会让不同结构产生相同签名。
- 误区：每次重复都加入答案。 通常只在出现次数等于 2 时加入，避免同类重复。
- 追问：为什么用后序？ 当前签名依赖左右子树签名，所以必须先处理孩子。
- 追问：字符串太慢怎么办？ 用三元组映射整数 ID，减少重复字符串拼接。
八、加强记忆
找重复子树的核心是“子树签名”。后序先拿左右签名，再拼当前签名；哈希表统计签名次数；第二次出现时记录答案。空节点标记是结构正确性的保险，不能省。