652. Find Duplicate Subtrees

weekly contest 43的签到题。

这题的解法告诉一个重要的道理：当执行完

..
dfs(root.left);
dfs(root.right);
..

这两句通常的dfs都会有的语句之后，代表着遍历的完成，回到了程序的入口处。

这题我一开始的思路是这样的，用任意一种order遍历二叉树，维护一个不重复的list里面存储所有第一次出现的node，然后每遇到一个node就用之前isSameTree那题的解法去list里用O(n)时间去对比有没有重复的，重复的话加入到结果集res；而且在res里还要再用O(n)判断一次，以防出现3个重复node的情况。这方法TLE了。

怎么避免用O(n)时间去对比呢？方法就是用Map。可是用map怎么存储TreeNode？毕竟存储的是hash，不同的Object的hashCode肯定是不同的，难道复写TreeNode hashCode()方法不成。。答案就是序列化成String。。

另外这题序列化只能用dfs不能用bfs，因为每个子节点都要对比。

另外，这题dfs只能用preorder或者postorder，inorder的话，如果node的value都一样，那么一个只有左子树的节点和一个只有右子树的节点的serialization是相同的。

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        if (root == null) return res;
        preorder(root, res, new HashMap<String, Integer>());
        return res;
    }

    private String preorder(TreeNode node, List<TreeNode> res, Map<String, Integer> map) {
        if (node == null) {
            return "#";
        }
        String serial = preorder(node.left, res, map) + "," + preorder(node.right, res, map) + "," + node.val;
        if (map.getOrDefault(serial, 0) == 1) {
            res.add(node);
        }
        map.put(serial, map.getOrDefault(serial, 0) + 1);

        return serial;
    }

--
ref:
https://leetcode.com/problems/find-duplicate-subtrees/discuss/