652. Find Duplicate Subtrees

Python

class Solution:
    def __init__(self):
        self.seem = set()
        self.result = []

    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.seem = set()
        self.result = dict()

        self.travel(root)

        return self.result.values()

    def travel(self, node: Optional[TreeNode]):
        if not node:
            return

        preorder_travel = tuple(self.get_subtree(node, []))
        if preorder_travel in self.seem:
            self.result[preorder_travel] = node # Prevent duplicate in result
        else:
            self.seem.add(preorder_travel)

        self.travel(node.left)
        self.travel(node.right)

    def get_subtree(self, node:  Optional[TreeNode], preorder: List):
        if not node:
            preorder.append(None)
            return

        preorder.append(node.val)
        self.get_subtree(node.left, preorder)
        self.get_subtree(node.right, preorder)
        return preorder