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/
