寻找重复子树

---

image.png

通过前序{root,left,right}或者后序{left,right,root,}获得子树的唯一描述，记得对null做“#”的标记，因为下面这个例子拼接的结果都是"00"，"00"，看不出来问题，但是对null做"#"标记可得：

前序："0#0##"，"00###"
后序："###00"，"##0#0"

中序："#0#0#"，"#0#0#"（中序即使标注也无法区分）

image.png

class Solution {
public:
    unordered_map<string,pair<TreeNode*,int>>m;
    vector<string> find(TreeNode*root){
        if(root==nullptr){
            return vector<string>{"#","#"};
        }
        vector<string> s1=find(root->left);
        vector<string> s2=find(root->right);

        string preorder=to_string(root->val)+s1[0]+s2[0];
        string inorder=s1[1]+to_string(root->val)+s2[1];

        if(m.count(preorder+inorder)==0){
            m[preorder+inorder]=make_pair(root,1);
        }
        else{
            m[preorder+inorder].second+=1;
        }
        return vector<string>{preorder,inorder};
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        find(root);
        vector<TreeNode*>res;
        for(auto i:m){
            if(i.second.second>1){
                res.push_back(i.second.first);
            }
        }
        return res;
    }
};

最优解：

但是其实只要前序遍历就能确定一个唯一的树了。不过为了避免 19 1 和 1 91拼接在一起分不清，建议加入","在拼接中间。

class Solution {
public:
    unordered_map<string,pair<TreeNode*,int>>m;
    string find(TreeNode*root){
        if(root==nullptr){
            return "#";
        }
        string s1=find(root->left);
        string s2=find(root->right);

        string preorder=to_string(root->val)+","+s1+","+s2;

        if(m.count(preorder)==0){
            m[preorder]=make_pair(root,1);
        }
        else{
            m[preorder].second+=1;
        }
        return preorder;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        find(root);
        vector<TreeNode*>res;
        for(auto i:m){
            if(i.second.second>1){
                res.push_back(i.second.first);
            }
        }
        return res;
    }
};