Find Duplicate Subtrees

1class Solution {
2    int id = 1;
3    Map<String, Integer> trees = new HashMap<>();
4    Map<Integer, Integer> count = new HashMap<>();
5    List<TreeNode> result = new ArrayList<>();
6
7    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
8        lookup(root);
9        return result;
10    }
11
12    private int lookup(TreeNode root) {
13        if (root == null) return 0;
14
15        // Serialize subtree
16        String serial = root.val + "," + lookup(root.left) + "," + lookup(root.right);
17
18        // Assign ID to serialized subtree
19        int treeId = trees.computeIfAbsent(serial, x -> id++);
20
21        // Count the occurrence of the tree ID
22        count.put(treeId, count.getOrDefault(treeId, 0) + 1);
23
24        // If it's the second occurrence of the same subtree, record it
25        if (count.get(treeId) == 2)
26            result.add(root);
27
28        return treeId;
29    }
30}