652.寻找重复的子树
给你一棵二叉树的根节点 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.遍历可以得到所有的子树, 对每个子树进行序列化
2.序列化的一般操作可以写成这样的字符串 “x(左子树序列化的结果)(右子树序列化的结果)”
3.在 set 中保存重复元素时, 必须保证不是统一个 node 的同一类 node 插入的是一个相同的结构, 用 set 保存已有的结果, 这里必须用一个 map 去保存已经见到过的结果; 如果用 set 直接保存 node, 那么相同的子树会保存不同的节点
class Solution {
private:
unordered_set<TreeNode*> repeat;
unordered_map<string, TreeNode*> seen;
public:
string dfs(TreeNode* node) {
if (node == nullptr) {
return "";
}
string serial = to_string(node->val) + "(" + dfs(node->left) + ")" + "(" + dfs(node->right) + ")";
auto it = seen.find(serial);
// 找到重复子树
if (it != seen.end()) {
repeat.insert(it->second);
// 注意这里只能插入统一类子树的标准化形式比如第一次存放的形式, 而不是插入node
// 不然会被判定为两个子树不一样
// repeat.insert(node);
} else {
seen[serial] = node;
}
return serial;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
vector<TreeNode*> ans;
ans.assign(repeat.begin(), repeat.end());
return ans;
}
};
297.二叉树的序列化与反序列化
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。示例 1：输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
示例 4：输入：root = [1,2] 输出：[1,2]
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
转载请注明来源, from goldandrabbit.github.io
