652. 寻找重复的子树

approach 1，DFS+哈希表

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        recursive(root);
        return res;
    }

    private StringBuilder recursive(TreeNode root) {
        if (root == null) return null;

        StringBuilder left = null;
        if (root.left != null) {
            left = recursive(root.left);
        }

        StringBuilder right = null;
        if (root.right != null) {
            right = recursive(root.right);
        }

        StringBuilder path = new StringBuilder();
        path.append("#").append(left).append("#").append(right).append("#").append(root.val);
        String key = path.toString();
        int cnt = map.getOrDefault(key, 0);
        if (cnt == 1) {
            res.add(root);
        }
        map.put(key, cnt+1);
        return path;
    }
}

以前写过的答案，序列化比上面做的更好

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        HashMap<String, Integer> map = new HashMap<>();
        List<TreeNode> res = new ArrayList<>();
        recursive(root, res, map);
        return res;
    }

    private String recursive(TreeNode node, List<TreeNode> res, HashMap<String, Integer> map) {
        if (node == null) {
            return "#";
        }

        String left = recursive(node.left, res, map);
        String right = recursive(node.right, res, map);

        String serialize = left +","+ right +","+ node.val;
        if (map.getOrDefault(serialize, 0) == 1) {
            res.add(node);
            map.put(serialize, map.get(serialize)+1);
        } else {
            map.put(serialize, map.getOrDefault(serialize, 0)+1);
        }

        return serialize;
    }

}