652. Find Duplicate Subtrees¶

Information¶

• Diffculty: Medium

• Created: 2020-02-08 19:59:00

• Last Motified: 2020-02-08 20:02:50

• Tags: Tree

Intuition¶

We could first serialize each subtree recursivly and then judge if the serialization of each subtree occurs more than once by string.count method.

Solution¶

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict

class Solution:
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
self.str = self._serialize(root)
self.ans = defaultdict(list)
self._find_duplicate(root)
return [v[0] for v in self.ans.values()]

def _serialize(self, node):
if node is None:
return ''
return '[%d](%s)(%s)' % (node.val,
self._serialize(node.left),
self._serialize(node.right))

def _find_duplicate(self, node):
if node is None:
return ''
s = '[%d](%s)(%s)' % (node.val,
self._find_duplicate(node.left),
self._find_duplicate(node.right))
if self.str.count(s) > 1:
self.ans[s].append(node)
return s
```