Topic:

Given a binary tree, return all repeated subtrees. For duplicate subtrees of the same class, you only need to return the root of any one of them.

When two trees are duplicated, they have the same structure and the same node value.

Example 1:1 / \ 2 3 / / \ 4 2 4/4 The following are two duplicate subtrees: 2/4 and 4Copy the code

Source: LeetCode link: leetcode-cn.com/problems/fi…

Analysis:

For finding duplicate subtrees, we mainly use map to store the number of current subtrees (serialized) as keys, mainly how to serialize and deserialize.

Code:

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; * /
class Solution
{
	// Record the current serialization number
    map<string.int> mp;
    // To store the sequence of nodes
    map<TreeNode*, string> visited;
    // To record the current serialized root node
    map<string, TreeNode*> ans;
    void dfs(TreeNode *root)
    {
        string tmp = to_string(root->val);
        if(! root->left && ! root->right) { mp[tmp]++; ans[tmp] = root; visited[root] = tmp; }else
        {
            if (root->left)
                dfs(root->left);
            if (root->right)
                dfs(root->right);
            stringvl = tmp + visited[root->left] + visited[root->right]; visited[root] = vl; ans[vl] = root; mp[vl]++; }}public:
    vector<TreeNode *> findDuplicateSubtrees(TreeNode *root)
    {
        
        vector<TreeNode *> v;
        if(! root)return v;
        visited[NULL] = "#";
        dfs(root);
        map<string.int>::iterator it = mp.begin();
        for(it; it ! = mp.end(); it++)if (it->second >= 2)
            {
                v.push_back(ans[it->first]);
            }
        returnv; }};Copy the code