Posted on 2023-02-28 22:15
Uriel 閱讀(61)
評論(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