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.
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.