LeetCode 652. 寻找重复的子树（DFS）

示例 1：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
下面是两个重复的子树：

      2
     /
    4
和

    4
因此，你需要以列表的形式返回上述重复子树的根结点。

class Solution {
	unordered_map<string, vector<TreeNode*>> m;
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if (root == NULL)
        	return {};
        vector<TreeNode*> ans;
        dfs(root);
        for(auto it = m.begin(); it != m.end(); ++it)
        {
        	if(it->second.size() != 1)
        		ans.push_back(it->second.front());
        }
        return ans;
    }
    string dfs(TreeNode* root) 
    {
        if(root == NULL)
            return "E";
    	string str = to_string(root->val)+dfs(root->left)+dfs(root->right);
    	//or
    	//string str = dfs(root->left)+dfs(root->right)+to_string(root->val);
    	//但是中序不可以
    	m[str].push_back(root);
    	return str;
    }
};