問題描述

給定一棵二叉樹，返回所有重復(fù)的子樹。對于同一類的重復(fù)子樹，你只需要返回其中任意一棵的根結(jié)點(diǎn)即可。
兩棵樹重復(fù)是指它們具有相同的結(jié)構(gòu)以及相同的結(jié)點(diǎn)值。

Example

輸入：[1,2,3,4,null,2,4,null,null,4]

輸出:[[2,4],[4]]

思路

對于一棵樹的子樹間的匹配問題，可以采用序列化 + 哈希表的方式來求解。通過對樹的序列化，并使用哈希表記錄對應(yīng)序列的出現(xiàn)次數(shù)。若當(dāng)前節(jié)點(diǎn) root 的序列化在哈希表中出現(xiàn)且僅出現(xiàn)過一次，則 root 就是我們要找的重復(fù)子樹

代碼

class Solution {
public:
    unordered_map<string, int> table;
    string helper(TreeNode* root, vector<TreeNode*>& ans){
        if(root == nullptr)
            return "#";
        string tmp = to_string(root->val) + " " + helper(root->left, ans) + " " + helper(root->right, ans);
        if(table[tmp] == 1){
            ans.push_back(root);
        }
        ++table[tmp];
        return tmp;
    }
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        vector<TreeNode*> ans;
        helper(root, ans);
        return ans;
    }
};

執(zhí)行結(jié)果： 76 ms, 49.6 MB