Given the root of a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them. Two trees are duplicate if they have the same structure with the same node values.
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]]
- code
class Solution:
# key the sub tree, value, value is count of this sub tree
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
if root is None:
return []
self.dic = {}
self.res = []
self.preorder(root)
return self.res
def preorder(self, root):
if root:
ls = str(root.val) + "-" + self.preorder(root.left) + "-" + self.preorder(root.right)
count = self.dic.get(ls, 0)
if count == 1:
self.res.append(root)
self.dic[ls] = count + 1
return ls
else:
return "#"