#652

Find Duplicate Subtrees

specialist · 705 · lc medium +30 · verified · 60.6% accepted · 6,115 likes · top 59%

Description

Given the root of a binary tree, find all subtrees that appear more than once (same structure and same node values). For each group of duplicates, return the root of one representative subtree. Return all such representative roots.

Example 1:

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

Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]

Output: [[1]]

Example 3:

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

Output: [[2,3],[3]]

Code

# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:

# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]: