题目描述
算法1
JAVA 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
HashMap<String, Integer> memo = new HashMap<>();
LinkedList<TreeNode> res = new LinkedList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traver(root);
return res;
}
String traver(TreeNode root){
if(root==null)return "#";
String right = traver(root.right);
String left = traver(root.left);
//序列化树
String SubTree = left+","+right+","+root.val;
int freq = memo.getOrDefault(SubTree, 0);
// 多次重复也只会被加入结果集一次
if(freq==1) res.add(root);
// 给子树对应的出现次数加一
memo.put(SubTree,freq+1);
return SubTree;
}
}