每日一练：2月18日精选题目解析

（2022.02.18）每日一题 寻找重复子树（框架思维的运用）

如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？

你需要知道以下两点：

1、以我为根的这棵二叉树（子树）长啥样？

2、以其他节点为根的子树都长啥样？

这就叫知己知彼嘛，我得知道自己长啥样，还得知道别人长啥样，然后才能知道有没有人跟我重复，对不对？

好，那我们一个一个来解决，先来思考，我如何才能知道以自己为根的二叉树长啥样？

要知道以自己为根的子树长啥样，得先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子？ （这就是后序遍历的框架思想）

1. 要解决以当前节点为根的二叉树长什么样，就得序列化它的结构（做记录）

   
   



2. 要知道以其它节点为根的二叉树长什么样，就得要把序列化二叉树的结构的结果存储起来（哈希表）

   class Solution {
private:
unordered_map record;
vector res;
public:
vector findDuplicateSubtrees(TreeNode* root) {
Traverse(root);
return res;
}
string Traverse(TreeNode* node){
if(node == nullptr){
return "#";
}
//后序遍历 + 序列化子树结构
string ans = Traverse(node->left)+","+Traverse(node->right)+","+ to_string(node->val);
record[ans]++;
if(record[ans]==2){
res.emplace_back(node);
}
return ans;
}
};

   

以上总结主要来自东哥的刷题笔记以及力扣。