题1：

652. 寻找重复的子树labuladong 题解思路

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

下面是两个重复的子树：

      2
     /
    4

和

    4

因此，你需要以列表的形式返回上述重复子树的根结点。

 

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     List<TreeNode> list=new ArrayList<>();
18     Map<String,Integer> map=new HashMap<>();
19     public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
20         build(root);
21         return list;
22     }
23 
24     public String build(TreeNode root) {
25         if (root==null) {
26             return "#";
27         }
28         String l=build(root.left);
29         String r=build(root.right);
30         String string=l+","+r+","+root.val;
31         int f=map.getOrDefault(string,0);
32         if (f==1) {
33             list.add(root);
34         }
35         map.put(string,f+1);
36         return string;
37     }
38 
39 }

思路：序列化树，左子树，右子树，根节点。空用#表示，用hashmap记录次数。