-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathfindDupSubTree.java
More file actions
32 lines (31 loc) · 923 Bytes
/
findDupSubTree.java
File metadata and controls
32 lines (31 loc) · 923 Bytes
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
26
27
28
29
30
31
32
import java.util.*;
public class findDupSubTree {
/*
preorder traverse: serialize tree , store them into a hash set
*/
Map<String, TreeNode> map;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
map = new HashMap<>();
Set<String> set = new HashSet<>();
ser(root, set);
//System.out.println(set);
List<TreeNode> list = new ArrayList<>();
for(String data : set){
list.add(map.get(data));
}
return list;
}
private String ser(TreeNode root, Set<String> res){
if(root == null) return "N,";
String leftTree = ser(root.left, res);
String rightTree = ser(root.right, res);
String data = root.val + "," + leftTree + rightTree;
if(map.containsKey(data)){
res.add(data);
}
else{
map.put(data, root);
}
return data;
}
}