# 寻找重复子树


## 题目描述
给你一棵二叉树的根节点 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，记录每个子树出现的次数（哈希，计数器）

### **为什么这个方法有效？**

1. **字符串描述唯一确定子树结构**  
    比如`"2,4,#,#,#"`只能对应一个二叉树（根->左->右）
    
2. **计数器精准捕捉重复**  
    当同一个字符串出现第二次时，说明结构完全相同的子树出现了两次。

### **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,#,#,#"`！


## 代码实现
```c++
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;

    }

};
```