Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
输出二叉树所有出现次数大于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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理