寻找重复的子树 图解题解

这道题到底在问什么

输入

根 50;左 30(挂叶 70);右 80(左 30 挂叶 70、右叶 70)

输出

重复子树: 叶子 [70] 与子树 [30→70]

输入

根 1(挂 1、1)

输出

重复子树: [1]

最优解：一步一步想明白

1. 3记住「后序把每棵子树序列化成唯一串、哈希计数、计数恰好等于 2 时记一个代表」,下面逐帧套它。
2. 4准备序列化先看整体思路。我们按后序走:先把左右子树都序列化好,再拼出当前节点的子树串,空节点用 # 占位。每拼出一个串,就丢进哈希表计数;哪个串的计数第一次到 2,就说明撞上重复子树了。
3. 5叶子节点后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。
4. 6指纹串成形把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。
5. 7计数 1串 70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。
6. 8左右已就绪后序走到节点 30(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 30 自己的子树串。
7. 9指纹串成形把 30 这棵子树拼成指纹串:30,70,#,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。
8. 10计数 1串 30,70,#,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。
9. 11叶子节点后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。
10. 12指纹串成形把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。
11. 13计数到 2串 70,#,# 的计数变成 2!这说明这棵子树之前出现过、现在重复了。按规则在计数恰好等于 2 这一刻,把当前节点 70(金色)记进答案,作为这种重复子树的代表。
12. 14左右已就绪后序走到节点 30(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 30 自己的子树串。
13. 15指纹串成形把 30 这棵子树拼成指纹串:30,70,#,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。
14. 16计数到 2串 30,70,#,#,# 的计数变成 2!这说明这棵子树之前出现过、现在重复了。按规则在计数恰好等于 2 这一刻,把当前节点 30(金色)记进答案,作为这种重复子树的代表。
15. 17叶子节点后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。
16. 18指纹串成形把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。
17. 19计数 3串 70,#,# 的计数到了 3。它在计数等于 2 的那次已经记过代表了,这里不再重复记,避免同一种子树记进答案多次。
18. 20左右已就绪后序走到节点 80(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 80 自己的子树串。
19. 21指纹串成形把 80 这棵子树拼成指纹串:80,30,70,#,#,#,70,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。
20. 22计数 1串 80,30,70,#,#,#,70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。
21. 23左右已就绪后序走到节点 50(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 50 自己的子树串。
22. 24指纹串成形把 50 这棵子树拼成指纹串:50,30,70,#,#,#,80,30,70,#,#,#,70,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。
23. 25计数 1串 50,30,70,#,#,#,80,30,70,#,#,#,70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。
24. 26得到答案整棵树后序遍历结束。一共找到 2 种重复子树:[70]、[30→70]。回头看,我们靠后序把每棵子树压成指纹串、用哈希表计数,计数第一次到 2 就记一个代表。遍历节点本身是一遍 O(n),但这里用完整字符串当 key,拼串和哈希的开销让最坏到 O(n²);要做到真正的 O(n),得把每种子串映射成一个整数 id、用 (左id,值,右id) 当 key,避免反复拼长串。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        from collections import defaultdict
        cnt=defaultdict(int); ans=[]
        def ser(n):
            if not n: return '#'
            s=f'{n.val},{ser(n.left)},{ser(n.right)}'
            cnt[s]+=1
            if cnt[s]==2: ans.append(n)
            return s
        ser(root); return ans

#include <algorithm>
#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<TreeNode*> findDuplicateSubtrees(TreeNode* root){ unordered_map<string,int> cnt; vector<TreeNode*> ans; function<string(TreeNode*)> ser=[&](TreeNode*n){ if(!n)return string("#"); string s=to_string(n->val)+","+ser(n->left)+","+ser(n->right); if(++cnt[s]==2)ans.push_back(n); return s;}; ser(root); return ans; }};

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ Map<String,Integer> cnt; List<TreeNode> ans; public List<TreeNode> findDuplicateSubtrees(TreeNode root){ cnt=new HashMap<>(); ans=new ArrayList<>(); ser(root); return ans;} String ser(TreeNode n){ if(n==null)return "#"; String s=n.val+","+ser(n.left)+","+ser(n.right); int c=cnt.getOrDefault(s,0)+1; cnt.put(s,c); if(c==2)ans.add(n); return s;} }

复杂度

面试官可能追问