Leetcode 652 Find Duplicate Subtrees

Problem:

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
Two trees are duplicate if they have the same structure with same node values.

Analysis:

1. Store all the nodes into an ArrayList. And compare each pair
2. serilize each node with the form:
   series = (root.val, < encoder root.left >, < encoder root.right >)
   In this way, each different node will have a unique series String
3. set ID number for each TreeNode
   we can use map.computeIfAbsent

Some basic knowledge

map.computeIfAbsent:
Object key = map.get(“key”);
if (key == null) {
key = new Object();
map.put(“key”, key);
}

// the above code is the same as:
Object key2 = map.computeIfAbsent(“key”, k -> new Object());

public class Solution1 {
	// method 2
	public List<TreeNode> findDuplicateSubtrees(TreeNode root){
		
		HashMap<String, Integer> counter = new HashMap<>();
		List<TreeNode> nodes = new ArrayList<TreeNode>();
		
		serilization(counter, nodes, root);
		return nodes;
	}
	
	public String serilization(HashMap<String, Integer> counter, List<TreeNode> nodes, TreeNode root){
		
		if (root == null) return "";
		String series = "(" + root.val + "," + serilization(counter, nodes, root.left) + "," + serilization(counter, nodes, root.right) + ")";
		counter.put(series, counter.getOrDefault(series, 0) + 1);
		if (counter.get(series) == 2) {
			nodes.add(root);
		}
		return series;
	}
	
	
	
	// method 3
	int t = 1;
	public List<TreeNode> findDuplicateSubtrees1(TreeNode root){
		
		
		HashMap<String, Integer> IDs = new HashMap<>();
		HashMap<Integer, Integer> counter = new HashMap<>();
		List<TreeNode> res = new ArrayList<>();
		
		setID(IDs, counter, res, root);
		
		return res;	
	}
	
	public int setID(HashMap<String, Integer> IDs, HashMap<Integer, Integer> counter, List<TreeNode> res,  TreeNode root){
		
		if (root == null) return 0;
		int leftNum = setID(IDs, counter, res,  root.left);
		int rightNum = setID(IDs, counter, res,  root.right);
		
		String nodeExpre = "(" + root.val + "," + leftNum + "," + rightNum + ")";
		int ID = IDs.computeIfAbsent(nodeExpre, x -> t++);
		counter.put(ID, counter.getOrDefault(ID, 0)+1);
		if (counter.get(ID) == 2) {
			res.add(root);
		}
		return ID;
		
	}	
	
}