Given 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 same node values.
Example 1:
image.png
序列化所有node，然后cnt
之前序列化树，因为必须先new出个node来（或者最后new），所以只能用preorder或者postorder，无法用inorder
这里也不能用inorder，因为无法还原出唯一的树，比如下面红圈圈出来的2部分
image.png
from collections import defaultdict
class Solution(object):
def findDuplicateSubtrees(self, root):
"""
:type root: TreeNode
:rtype: List[TreeNode]
"""
d = defaultdict(list)
def stringfy(r):
if not r: return '#'
s = '%s,%s,%s'%(stringfy(r.left),str(r.val),stringfy(r.right))
d[s].append(r)
return s
stringfy(root)
return [d[k][0] for k in d if len(d[k])>1]
但是可以人为指定是左还是右，这样还原起来会比较麻烦就是
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_set<string> exist, used;
vector<TreeNode*> result;
inorder(root, exist, used, result);
return result;
}
private:
string inorder(TreeNode* root, unordered_set<string>& exist, unordered_set<string>& used, vector<TreeNode*>& result) {
if (!root) return "";
string left = inorder(root->left, exist, used, result);
string right = inorder(root->right, exist, used, result);
string all = "l" + left + "m" + to_string(root->val) + "r" + right;
if (exist.count(all) && !used.count(all)) {
result.push_back(root);
used.insert(all);
}
exist.insert(all);
return all;
}
};
