Sponsored
Sponsored
Utilize a Depth-First Search (DFS) strategy and serialize each subtree. Treat the serialization as a key in a hashmap to track occurrences of identical subtrees. Duplicate entries are detected when a serialized key is encountered more than once.
Time Complexity: O(N), where N is the number of nodes since we visit each node once.
Space Complexity: O(N), accounting for the hashmap to store serialized trees and recursion stack space.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def findDuplicateSubtrees(self, root: TreeNode):
9 from collections import defaultdict
10 def serialize(node):
11 if not node:
12 return '#'
13 serial = f'{node.val},{serialize(node.left)},{serialize(node.right)}'
14 count[serial].append(node)
15 return serial
16
17 count = defaultdict(list)
18 serialize(root)
19 return [nodes[0] for nodes in count.values() if len(nodes) > 1]This Python solution uses DFS to serialize each subtree into a string. These strings are stored in a dictionary. If a string appears more than once, it indicates a duplicate subtree. The function returns one node from each set of duplicates.
Rather than using direct serialization strings, assign each unique subtree encountered a unique ID using a hash map. If a subtree's ID is seen again, it's a duplicate.
Time Complexity: O(N), as we traverse each node.
Space Complexity: O(N), necessary for dictionaries and recursive processing space.
1import java.util.*;
This Java solution assigns unique identifiers to subtrees using a map, incrementing identifiers for new structures. Duplicate subtree roots are added to the result list when repeated IDs are found.