Find Duplicate Subtrees Python Solution

lcpy gen -n 652   # by problem number
lcpy gen -s find_duplicate_subtrees   # by problem name

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Input: root = [2,1,1]
Output: [[1]]

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

from collections import Counter

from leetcode_py import TreeNode


class Solution:
    # Time: O(n^2) worst case for string serializations
    # Space: O(n^2)
    def find_duplicate_subtrees(self, root: TreeNode[int] | None) -> list[TreeNode[int] | None]:
        counts: Counter[str] = Counter()
        result: list[TreeNode[int] | None] = []

        def serialize(node: TreeNode[int] | None) -> str:
            if node is None:
                return "#"
            key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            counts[key] += 1
            if counts[key] == 2:
                result.append(node)
            return key

        serialize(root)
        return result