Find Duplicate Subtrees

Question

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Solution

其實這題不會很難想，但第一次寫用錯的方法所以寫不出來。我用了 (Integer, List<>)，List 裡面存 TreeNode，到後面用 for (int num : map.keySet()) 取出來去比 root.val 一樣時，TreeNode 一不一樣。這樣會造成我有一樣數值的 node 被加進最後輸出的 list 裡面，原因是我無法用 list.contains(TreeNode) 來判斷。 因此解答用 serialize，把每一個 node 所生成的 tree 都 serialize 成一組字串，去比較字串就會是獨一無二了

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, List<TreeNode>> map = new HashMap<String, List<TreeNode>>();
        List<TreeNode> dups = new ArrayList<TreeNode>();
        serialize(root, map);
        for (List<TreeNode> group : map.values()) {
            if (group.size() > 1) dups.add(group.get(0));
        }
        return dups;
    }

    private String serialize(TreeNode node, Map<String, List<TreeNode>> map) {
        if (node == null) return "";
        String s = "1" + serialize(node.left, map) + node.val + serialize(node.right, map) + "2";
        if (!map.containsKey(s)) map.put(s, new ArrayList<TreeNode>());
        map.get(s).add(node);
        return s;
    }