## Challenge#

Given the root of a binary tree, return all duplicate subtrees. You only need to return the root of any of them.

## Solution#

``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:

def __init__(self):
self.all_node = []
self.ans = []
self.s = set()

def preorder(self, root, arr):

arr.append(root.val)

if root.left:
self.preorder(root.left, arr)
else:
arr.append(None)

if root.right:
self.preorder(root.right, arr )
else:
arr.append(None)
return arr

def get_subtree(self, root):
res = [self.preorder(root, []), root]
current, root = res

if current in self.all_node and tuple(current) not in self.s:
self.ans.append(root)
else:
self.all_node.append(current)

def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
queue = [root]
while queue:
node = queue.pop(0)
self.get_subtree(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return self.ans
``````

Time Complexity: O(n^2)