652.寻找重复的子树

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

思路：分解问题（后序）

//定义：输入一个结点，返回以该结点为根的子树的序列化字符串
string findString(TreeNode* root,vector& v,unordered_map& mapping) 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //定义：输入一个结点，返回以该结点为根的子树的序列化字符串
    string findString(TreeNode* root,vector& v,unordered_mapint>& mapping)
    {
        if(root==nullptr)
        return "#";
        string left=findString(root->left,v,mapping);
        string right=findString(root->right,v,mapping);
        string str=left+","+right+","+to_string(root->val);//以前序或后序拼接序列化字符串，但是不能以中序拼接字符串
        mapping[str]++;
        if(mapping[str]==2)//如果同一序列化字符串出现了两次,说明有重复的子树;如果大于2,只需要返回其中任意一棵的根结点即可, 无需重复添加根节点
        {
            v.push_back(root);
        }
        return str;
    }
    vector findDuplicateSubtrees(TreeNode* root) {
        unordered_mapint> mapping;//mapping(子树序列化的字符串，出现的次数)
        vector v;
        findString(root,v,mapping);
        return v;
    }
};

为什么不能用中序序列化的字符串（左根右）？

      0                        0

   /                                \

0                                     0

这两个子树不相同，但是它们的中序序列化的字符串相同，均为#0#0#，故不能采用

而前序与后序序列化的字符串就不相同，可以采用。