category-wise-problems

contains category wise problems(data structures, competitive) of popular platforms.

View the Project on GitHub mayankdutta/category-wise-problems

652. Find Duplicate Subtrees

Based upon the Post order traversal AND serialize deserialize, HOW?

subtree always involves leaves therefore evolving from leaf seems better idea.
In post order priority is given to left, right then to leaf.

class Solution {
    HashMap<String, Integer> map;
    ArrayList<TreeNode> arr;
    
    public String pre(TreeNode root) {
        if (root == null) 
            return "#";
        
        String left = pre(root.left);
        String right = pre(root.right);
        
        String curr = left + "," + right + "," + Integer.toString(root.val);
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        if (map.get(curr) == 2) 
            arr.add(root);
        
        return curr;
    }
    
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        arr = new ArrayList<>();
        String ans = pre(root);
        return arr;
    }
}