652. Find Duplicate Subtrees --- M

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

 

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

 

Constraints:

• The number of the nodes in the tree will be in the range [1, 5000]
• -200 <= Node.val <= 200

A:

错误的解法

/**

* 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:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_set<string> S;

unordered_map<string, TreeNode*> map;

helper(root, S, map);

vector<TreeNode*> res;

for(auto p : map){

res.push_back(p.second);

}

return res;

}

private:

string helper(TreeNode* root, unordered_set<string>& S, unordered_map<string, TreeNode*> &map){

if(!root)

return "";

auto l = helper(root->left, S, map);

auto r = helper(root->right,S, map);

auto node = l+"-"+to_string(root->val)+"-"+r;

if(S.find(node) != S.end()){

map[node] = root;

}else{

S.insert(node);

}

return node;

}

};

上述错误的原因是： 基于 inorder的表示方法。 string方法不唯一。

Given. [0,0,0,0,null,null,0,null,null,null,0]

上面的算法会算出： [[0,null,0],[0]]

而正确答案是 [[0]]

而正确的做法只需要改一行

auto node = "("+l+")"+to_string(root->val)+"("+r + ")";