Given the root&nbsp;of 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 the same node values.

&nbsp;
Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]


Example 2:

Input: root = [2,1,1]
Output: [[1]]


Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]


&nbsp;
Constraints:


	The number of the nodes in the tree will be in the range [1, 10^4]
	-200 &lt;= Node.val &lt;= 200


class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        ans = []
        path_map = {}
        
        def dfs(node):
            if not node:
                return "#"
            
            path = ",".join([str(node.val), dfs(node.left), dfs(node.right)])
            
            if path in path_map:
                path_map[path] += 1
                if  path_map[path] == 2:
                    ans.append(node)
            else:
                path_map[path] = 1
                
            return path
        
        
        dfs(root)
        return ans
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        HashSet<String> hashes = new HashSet<String>();
        HashSet<String> added = new HashSet<String>();

        // for each node, perform a dfs traversal and generate a hash
        // check if the hash already exists in a set,
        // if it does, get the treenode and add it to the list
        Stack<TreeNode> s = new Stack<TreeNode>();

        s.add(root);
        while(!s.isEmpty()){
            TreeNode tmp = s.pop();
            dfs(tmp, "", tmp, list, hashes, added);

            if(tmp.left != null){
                s.add(tmp.left);
            }
            if(tmp.right != null){
                s.add(tmp.right);
            }
        }

        return list;

    }

    public void dfs(TreeNode parent, String hash, TreeNode root, List<TreeNode> list, HashSet<String> set, HashSet<String> added){

        Stack<TreeNode> stack = new Stack<TreeNode>();

        stack.add(root);
        //String hash = "";
        hash += root.val + "ROOT,";
        while(!stack.isEmpty()){
            TreeNode tmp = stack.pop();
            //hash += tmp.val + ",";

            if(tmp.left != null){
                hash += tmp.left.val + "L,";
                stack.add(tmp.left);
            }
            else{
                hash+= "NULLL,";
            }
            if(tmp.right != null){
                hash += tmp.right.val + "R,";
                stack.add(tmp.right);
            }
            else{
                hash+="NULLR,";
            }
            if(tmp.left == null && tmp.right == null && stack.isEmpty()){
                if(set.contains(hash)){
                    if(!added.contains(hash)){
                        list.add(parent);
                        added.add(hash);
                    }
                }
                else{
                    set.add(hash);
                }
                return;
            }

        }
    }
}
class Solution {
public:
    unordered_map<string,int> dp ;
    vector<TreeNode*> ans ;

    string solve(TreeNode * root){
        if(!root) return "" ;

        string left = solve(root->left) ;
        string right = solve(root->right) ;

        string code = to_string(root->val) + " " + left + " " + right ;
        if(dp[code] == 1) ans.push_back(root) ;
        dp[code]++ ;

        return code ;
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        string dummy = solve(root) ;
        return ans ;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function(root) {
    let stack = [];
    let result = [];
    let hashTable = {};
    stack.push(root);
    while (stack.length) {
        let node = stack.pop();
        let treeToArr = dfsArr(node);
        if (node.right) {
            stack.push(node.right);
        }
        if (node.left) {
            stack.push(node.left);
        }
		// If sub tree has not been seen, set to one.
		// If sub tree has been seen, increment number.
        hashTable[treeToArr] = hashTable[treeToArr] ? 
            { num: hashTable[treeToArr].num + 1, ref: node} :
            { num: 1, ref: node};
    }
	// Builds result array with duplicate trees seen
    for (let i in hashTable) {
        if (hashTable[i].num > 1) {
            result.push(hashTable[i].ref);
        }
    }
    return result;
};

// Post order of subtree stored in array
function dfsArr (node) {
    let stack = [];
    let result = [];
    stack.push(node);
    while (stack.length) {
        let node = stack.pop();
        node ? result.push(node.val) : result.push(null);
        if (!node) continue;
        if (node.right) {
            stack.push(node.right);
        } else {
            stack.push(null);
        }
        if (node.left) {
            stack.push(node.left);
        } else {
            stack.push(null);
        }
    }
    return result;
}
Find Duplicate Subtrees