题目描述
给你一棵二叉树的根节点 root ,返回所有 重复的子树 。
对于同一类的重复子树,你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ,则认为二者是 重复 的。
样例
示例1
输入:root = [1,2,3,4,null,2,4,null,null,4]
输出:[[2,4],[4]]
示例2
输入:root = [2,1,1]
输出:[[1]]
示例3
输入:root = [2,2,2,3,null,3,null]
输出:[[2,3],[3]]
算法1
(前序遍历+hash表) $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 {
public:
unordered_map<string, int> hash;
vector<TreeNode*> res;
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
return res;
}
string dfs(TreeNode* root)
{
if (!root) return "#";
auto left = dfs(root->left);
auto right = dfs(root->right);
string tree = to_string(root->val) + ',' +left + ',' +right;
hash[tree] ++;
if (hash[tree] == 2) res.push_back(root);
return tree;
}
};
算法2
(前序遍历 + 2遍hash) $O(n)$
使用 unordered_map
记录每个子树经过哈希后的数量,哈希方法可以用最简单的前序遍历,即根,左子树,右子树的方式递归构造。逗号和每个叶子结点下的空结点的位置需要保留。
若发现当前子树在哈希表第二次出现,则将该结点记入答案列表。
时间复杂度
-
每个结点仅遍历一次,
unordered_map
单次操作的时间复杂度为$O(1)$。 -
但遍历结点中,可能要拷贝当前字符串到答案,将需要拷贝的字符串先映射为唯一ID,然后只拷贝ID,另外再使用一次hash记录次ID出现次数,拷贝的时间复杂度为 $O(1)$,总时间复杂度为 $O(n)$。
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 {
public:
unordered_map<string, int> hash;
unordered_map<int, int> count;
vector<TreeNode*> res;
int cnt = 0; // 不重复唯一ID,用来代表子树字符串
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
hash["#"] = cnt ++;
dfs(root);
return res;
}
string dfs(TreeNode* root)
{
if (!root) return to_string(hash["#"]);
auto left = dfs(root->left);
auto right = dfs(root->right);
string tree = to_string(root->val) + ',' +left + ',' +right;
if(!hash.count(tree)) hash[tree] = cnt ++;
int t = hash[tree];
count[t] ++;
if (count[t] == 2) res.push_back(root);
return to_string(t);
}
};