原题链接:
https://leetcode.cn/problems/find-duplicate-subtrees/
对于每一种子树以一个三元组进行编号
(node.val,l,r) —> (node,idx)
node.val为节点的值 l,r 为左右子树的编号
node 为节点 idx为该节点的编号
这样当我们每发现一种新的子树 那么就给这个子树编号 否则就将该子树 加入结果 与相同的共用一个编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# 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]]:
        # 用于记录节点的 编号
        # 三元组 -> 节点编号
        # (v,l,r) -> (node,idx)
        seen = dict()
        # 记录结果
        repeat = set()
        
        idx = 0

        def dfs(node):
            if not node:
                return 0
            
            tri = (node.val,dfs(node.left),dfs(node.right)) 

            if tri in seen:
                (tree,index) = seen[tri]
                repeat.add(tree)
                # 重复出现的树 所以共用一个编号 
                return index
            else:
                nonlocal idx 
                idx = idx + 1
                seen[tri] = (node,idx)
                # 新出现的树 需要新的编号
                return idx
            
        dfs(root)
		# 这里返回的时候注意 转换为list
        return list(repeat)