27. Find Duplicate Subtrees

Given the root 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.

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]]

Solution: (Use Serialization)

Approach: Two tree are same if they have the same structure along with same node values. So we can serialize a tree: So same tree have same serialized string and we can use map to store it.

Performing Postorder traversal and strong the string of root node as Node->val , left subtree, right subtree and NULL represented with #

class Solution
{
public:
    unordered_map<string, vector<TreeNode *>> m;

    string serialize(TreeNode *root, string s)
    {

        if (root == NULL)
        {
            return "#";
        }

        string lt = serialize(root->left, s);
        string rt = serialize(root->right, s);

        string res = to_string(root->val) + ',' + lt + ',' + rt;
        m[res].push_back(root);
        return res;
    }
    
    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root)
    {
        vector<TreeNode *> res;
        if (root == NULL)
        {
            return res;
        }
        serialize(root, "");

        for (auto itr = m.begin(); itr != m.end(); itr++)
        {

            if (itr->second.size() > 1)
            {
                res.push_back(itr->second[0]);
            }
        }

        return res;
    }
};

Time Complexity: O(n)