1、前言
题目描述
2、思路
这道题的意思一开始确实难以理解，什么叫重复子树？
重复子树说的是两个子树具有相同的结构，而且值相同。也就是说，一个为左子树，那么另一个一定为左子树，且对应节点上的值是一模一样的。然后根据这种定义参考题目的示例。
这道题考一个后续遍历，我理解二叉树的后续遍历是一个自底向上的过程（即先遍历到最深入的一个节点再依次向上返回），与之相反的先序遍历则是一个自顶向下的过程。
那么我们就根据后续遍历，一直到底部，然后将此节点变成字符串存储起来，只要遇到相同的就把节点记录下来。因为相同的节点可以有多个，所以只记录重复次数为1的。
3、代码
class Solution {
Map<String, Integer> map = new HashMap<>();
List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return res;
}
private String dfs(TreeNode root) {
if(root == null) {
return "#";
}
String left = dfs(root.left);
String right = dfs(root.right);
String subTree = left + "," + right + "," + root.val;
int times = map.getOrDefault(subTree, 0);
if(times == 1){
res.add(root);
}
map.put(subTree, map.getOrDefault(subTree, 0) + 1);
return subTree;
}
}
