Posted on 2023-02-28 22:15
Uriel 阅读(27)
评论(0) 编辑 收藏 引用 所属分类:
搜索 、
数据结构 、
闲来无事重切Leet Code 、
Hash
输出二叉树所有出现次数大于1的子数
DFS，用Counter()记录每一种子树出现次数（将子树先序遍历并且转化为字符串）
1 #652
2 #Runtime: 43 ms (Beats 62%)
3 #Memory: 20.1 MB (Beats 78%)
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def findDuplicateSubtrees(self, root):
13 """
14 :type root: TreeNode
15 :rtype: List[TreeNode]
16 """
17
18 ans = []
19 cnt = collections.Counter()
20
21 def DFS(r):
22 if not r:
23 return ''
24 tree_str = str(r.val) + '.' + DFS(r.left) + '.' + DFS(r.right)
25 if cnt[tree_str] == 1:
26 ans.append(r)
27 cnt[tree_str] += 1
28 return tree_str
29
30 DFS(root)
31 return ans