寻找重复子树
目录
题目描述
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
https://assets.leetcode.com/uploads/2020/08/16/e1.jpg
输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[2,4],[4]]
解题思路
使用后序遍历+哈希！
思路： 1，给每个子树一个“身份证”（后序遍历的字符串） 2，记录每个子树出现的次数（哈希，计数器）
为什么这个方法有效？
字符串描述唯一确定子树结构
比如"2,4,#,#,#"只能对应一个二叉树（根->左->右）计数器精准捕捉重复
当同一个字符串出现第二次时，说明结构完全相同的子树出现了两次。
1. 为什么想到用字符串表示子树？
- 直观需求：判断两棵子树是否相同，需要比较它们的完整结构（包括节点值和左右子树）。
- 字符串的特性：
字符串可以唯一编码一棵树的结构（比如"2,#,#"只能对应一个单节点2的子树）。 - 递归的天然适配：
树的遍历本身就是递归的，而字符串拼接也天然适合递归（左+右+根=完整结构）。
2. 为什么用后序遍历？
- 后序（左→右→根）的顺序：
只有先知道左右子树的序列化结果，才能拼接当前子树的字符串。
（比如必须先知道4,#,#和#，才能拼出2,4,#,#,#）
3. 为什么用哈希表（或计数器）？
- 快速判重：
当序列化字符串第二次出现时，说明遇到了结构完全相同的子树。
（哈希表能在O(1)时间内判断是否重复，比暴力遍历高效得多）
4. 为什么空节点要用 # 表示？
- 避免歧义：
比如子树2的左为空、右为3，序列化为"2,#,3,#,#"；
如果不用#，"2,3"可能被误认为是2的左为3。
5. 这个方法的灵感来源
- 数据库中的“序列化”：
类似把复杂数据转换成字符串存储（如JSON）。 - 编译器中的“语法树”：
编译代码时会用字符串哈希优化语法树的重复结构检测。 - 人类的自然思维：
想象你要向别人描述一棵树的结构，你会怎么说？
→ “根是2，左是4，右是空” → 正好对应"2,4,#,#,#"！
代码实现
class Solution {
public:
vector<string> all_subtrees; // 存储所有子树的序列化字符串
unordered_map<string, int> count; // 记录每个序列出现的次数
vector<TreeNode*> result; // 存储重复子树的根节点
string serialize(TreeNode* node) {
if (node == nullptr) return "#";
string left = serialize(node->left);
string right = serialize(node->right);
// 当前子树的序列化表示
string subtree = to_string(node->val) + "," + left + "," + right;
// 检查是否已经出现过
if (count[subtree] == 1) {
result.push_back(node);
}
count[subtree]++;
return subtree;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
serialize(root);
return result;
}
};