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) ...