【Java|golang】652. 寻找重复的子树---dfs遍历

给定一棵二叉树 root，返回所有重复的子树。

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

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
示例 2：

输入：root = [2,1,1]
输出：[[1]]
示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

树中的结点数在[1,10^4]范围内。
-200 <= Node.val <= 200

Map<String,Integer> map=new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
       dfs(root);
       return res;
    }
    public String dfs(TreeNode root){
         if (root==null){
             return "#";
         }
         String s=root.val+";"+dfs(root.left)+";"+dfs(root.right);
        Integer n = map.getOrDefault(s, 0);
        if(n==1){
            res.add(root);
        }
        map.put(s,n+1);
        return s;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var mapKV map[string]int
var res []*TreeNode

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    mapKV=make(map[string]int,0)
	res=make([]*TreeNode,0)
	dfs(root)
	return res
}
func dfs(root *TreeNode) string{
	if root==nil {
		return "#"
	}
	s:= fmt.Sprintf("%d;%s;%s", root.Val, dfs(root.Left), dfs(root.Right))
    v,ok:=mapKV[s]
	if ok {
		if v==1 {
			res= append(res, root)
		}
        mapKV[s]++
	}else {
		mapKV[s]=1
	}
	return s
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25