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.
1function TreeNode(val)
This JavaScript approach assigns unique identifiers for each different subtree structure encountered. Duplicate IDs signal subtrees that share the same structure and value arrangements.