Untitled
import java.util.*; class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public List<TreeNode> findDuplicateSubtrees(TreeNode root) { List<TreeNode> result = new ArrayList<>(); Map<String, Integer> subtreeMap = new HashMap<>(); serializeTree(root, subtreeMap, result); return result; } private String serializeTree(TreeNode node, Map<String, Integer> subtreeMap, List<TreeNode> result) { if (node == null) return "#"; // Base case: null nodes are serialized as "#" // Serialize the current subtree String serialized = node.val + "," + serializeTree(node.left, subtreeMap, result) + "," + serializeTree(node.right, subtreeMap, result); // Update the frequency of this serialization subtreeMap.put(serialized, subtreeMap.getOrDefault(serialized, 0) + 1); // If this is the second time we've seen this serialization, add the node to the result if (subtreeMap.get(serialized) == 2) { result.add(node); } return serialized; } }
Leave a Comment