輸出二叉樹所有出現(xiàn)次數(shù)大于1的子數(shù)
DFS，用Counter()記錄每一種子樹出現(xiàn)次數(shù)（將子樹先序遍歷并且轉(zhuǎn)化為字符串）
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