Find duplicate subtrees

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)
            self.s.add(tuple(current))
        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)

Challenge#

Solution#

Challenge

Solution