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.
1import java.util.*;
2
3public class Solution {
4 public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
5 Map<String, List<TreeNode>> map = new HashMap<>();
6 serialize(root, map);
7 List<TreeNode> result = new ArrayList<>();
8 for (List<TreeNode> nodes : map.values()) {
9 if (nodes.size() > 1) {
10 result.add(nodes.get(0));
11 }
12 }
13 return result;
14 }
15
16 private String serialize(TreeNode node, Map<String, List<TreeNode>> map) {
17 if (node == null) {
18 return "#";
19 }
20 String serial = node.val + "," + serialize(node.left, map) + "," + serialize(node.right, map);
21 map.computeIfAbsent(serial, k -> new ArrayList<>()).add(node);
22 return serial;
23 }
24}This Java solution involves recursively serializing each subtree and storing the serialized string in a hashmap. Duplicates are identified by checking the hashmap for strings that occur more than once.
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.
1class TreeNode:
2
This Python approach maps each subtree structure to a unique identifier, incrementally assigning IDs using a dictionary. Duplicates are recognized when the same ID appears multiple times.