寻找重复的子树

记住「后序把每棵子树序列化成唯一串、哈希计数、计数恰好等于 2 时记一个代表」,下面逐帧套它。

后序遍历 · 开始：先看整体思路。我们按后序走:先把左右子树都序列化好,再拼出当前节点的子树串,空节点用 # 占位。每拼出一个串,就丢进哈希表计数;哪个串的计数第一次到 2,就说明撞上重复子树了。

后序到达 70：后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。

序列化 70：把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。

计数 70：串 70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。

后序到达 30：后序走到节点 30(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 30 自己的子树串。

序列化 30：把 30 这棵子树拼成指纹串:30,70,#,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。

计数 30：串 30,70,#,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。

后序到达 70：后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。

序列化 70：把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。

命中重复! 70：串 70,#,# 的计数变成 2!这说明这棵子树之前出现过、现在重复了。按规则在计数恰好等于 2 这一刻,把当前节点 70(金色)记进答案,作为这种重复子树的代表。

后序到达 30：后序走到节点 30(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 30 自己的子树串。

序列化 30：把 30 这棵子树拼成指纹串:30,70,#,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。

命中重复! 30：串 30,70,#,#,# 的计数变成 2!这说明这棵子树之前出现过、现在重复了。按规则在计数恰好等于 2 这一刻,把当前节点 30(金色)记进答案,作为这种重复子树的代表。

后序到达 70：后序走到叶子 70(紫色)。叶子没有左右孩子,两边都记成 #,马上把它拼成指纹串。

序列化 70：把 70 这棵子树拼成指纹串:70,#,#。叶子两边是空,所以是 70,#,#。

计数 70：串 70,#,# 的计数到了 3。它在计数等于 2 的那次已经记过代表了,这里不再重复记,避免同一种子树记进答案多次。

后序到达 80：后序走到节点 80(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 80 自己的子树串。

序列化 80：把 80 这棵子树拼成指纹串:80,30,70,#,#,#,70,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。

计数 80：串 80,30,70,#,#,#,70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。

后序到达 50：后序走到节点 50(紫色)。因为是后序,它的左右子树这时都已经序列化完了,可以直接用两边的串拼出 50 自己的子树串。

序列化 50：把 50 这棵子树拼成指纹串:50,30,70,#,#,#,80,30,70,#,#,#,70,#,#。可以看到它内嵌了左右两段子串,结构一不同串就不同。

计数 50：串 50,30,70,#,#,#,80,30,70,#,#,#,70,#,# 第一次出现,计数记为 1。还不是重复,标记成已处理(绿色),继续后序遍历。

全部访问完成：整棵树后序遍历结束。一共找到 2 种重复子树:[70]、[30→70]。回头看,我们靠后序把每棵子树压成指纹串、用哈希表计数,计数第一次到 2 就记一个代表。遍历节点本身是一遍 O(n),但这里用完整字符串当 key,拼串和哈希的开销让最坏到 O(n²);要做到真正的 O(n),得把每种子串映射成一个整数 id、用 (左id,值,右id) 当 key,避免反复拼长串。

边界:空树/无重复都返回空;同种多次只记一个代表。

两个追问:后序保证先有子串;用子树 id 替代长串可降到 O(n)。