题目描述
给定一棵二叉树 root，返回所有 重复的子树。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值，则它们是 重复 的。
样例
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
输入：root = [2,1,1]
输出：[[1]]
输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]
限制
- 树中的结点数在
[1, 10^4]范围内。 -200 <= Node.val <= 200
算法
(前序遍历，哈希表) $O(n^2)$
- 使用
unordered_map记录每个子树经过哈希后的数量，哈希方法可以用最简单的前序遍历，即根,左子树,右子树的方式递归构造。逗号和每个叶子结点下的空结点的位置需要保留。 - 若发现当前子树在哈希表第二次出现，则将该结点记入答案列表。
时间复杂度
- 每个结点仅遍历一次，
unordered_map单次操作的时间复杂度为 $O(1)$。 - 但遍历结点中，可能要拷贝当前字符串到答案，拷贝的时间复杂度为 $O(n)$，故总时间复杂度为 $O(n^2)$。
C++ 代码
/**
* 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 {
private:
string solve(TreeNode *r, unordered_map<string, int> &hash, vector<TreeNode*> &ans) {
if (r == NULL)
return "";
string cur = "";
cur += to_string(r -> val) + ",";
cur += solve(r -> left, hash, ans) + ",";
cur += solve(r -> right, hash, ans);
hash[cur]++;
if (hash[cur] == 2)
ans.push_back(r);
return cur;
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_map<string, int> hash;
vector<TreeNode*> ans;
solve(root, hash, ans);
return ans;
}
};
先序遍历相同的二叉树并不一定结构也相同吧？感觉用先序遍历的序列来作为key表达二叉树会有问题。
这里的前序遍历和普通的前序遍历稍有区别，由于有逗号的存在，会把空节点空出来，这样就可以用前序遍历唯一确定一棵二叉树了。具体可以参考LeetCode 331.
题解描述已修正。
写得太好了，甚至有点感动得想哭
太牛逼了，有点像rolling hash。楼主真是融会贯通，游刃有余。
写了两种方法，为什么传引用时候会出错而按返回值返回时就正常了
如果 $s$ 是引用，则相当于全局变量，递归回溯后，$s$ 是所有已遍历节点的哈希值，并不是当前子树的哈希值
明白了，谢谢大佬~
这题用中序遍历做哈希值会冲突
大佬，你好，想问一下这里为啥是ans.push_back(r), 那结果里面不就是只有单个单个的节点嘛
ans数组是个结点数组，每个元素都是一棵树的根结点多谢大佬，我已经知道啦hh
这个题的意思是不是：只要是重复，不管重复多少次，返回重复的结构就行；
因为看最后的hash表显示
4这个结构的次数是3。而4这个结构第一次出现hash[cur] == 2的位置是在2，4这个结构里面。对滴
OK！谢谢zc大佬。
每棵子树对应的字符串的长度是 $O(n)$的，所以这个做法应该是 $O(n^2)$ 的吧hh
对，答案还要进行 copy，已修正
棒啊
但遍历结点中，可能要拷贝当前字符串到答案，拷贝的时间复杂度为 $O(n)$，故总时间复杂度为$ O(n^2)$。
yls,这里的拷贝是指下面的”+”吗？$+$的时间复杂度是o(n)的吗？
string的加法可以看成先分配一段空间，然后把原字符串复制过去。另外dfs的返回值是string的赋值操作，也会把string复制一遍，都是线性的复杂度。
返回会有RVO优化，所以实际复杂度可能并没有这么高
为什么这里要加逗号哇？
为了防止数字连在一起造成混淆
C++中string 拼接是O(1)的嘛？
cur += to_string(r -> val) + “,”;
cur += dfs(r -> left, hash, ans) + “,”;
cur += dfs(r -> right, hash, ans);
就是这里。
这种方法用java写的话是O(N^2),因为每个node拼接是O(N)的。而且，严格说，java里，string的hash也不是O(1)的
想问一下，如果建立一个哈希表unordered_map[HTML_REMOVED] hash，把子树当作key，每个子树都是唯一的呢？
已在问答区回答。652题 TreeNode作为哈希表中key的问题