[leetcode-652-Find Duplicate Subtrees]
2024-08-26 07:23:13
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any oneof them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:
1
/ \
2 3
/ / \
4 2 4
/
4
The following are two duplicate subtrees:
2
/
4
and
4
Therefore, you need to return above trees' root in the form of a list.
思路:
将每一个节点的左子节点的值和右结点的值都存储下来,组成一个字符串,作为索引,将对应节点保存到map里。
string serialize(TreeNode* root,unordered_map<string,vector<TreeNode*> >& mp)
{
if(root==nullptr) return "";
string s= "(" + serialize(root->left,mp) + to_string(root->val) + serialize(root->right,mp) + ")";
mp[s].push_back(root);
return s;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root)
{
unordered_map<string,vector<TreeNode*> >mp;
vector<TreeNode*>ret;
serialize(root,mp);
for(auto it = mp.begin();it != mp.end();it++)
{
if(it->second.size() > ) ret.push_back(it->second[]);
}
return ret;
}
参考:
https://discuss.leetcode.com/topic/97601/c-clean-code
最新文章
- 在脚本中使用sudo命令,将密码保存在脚本中,不需要手动输入密码
- 【leetcode❤python】 7. Reverse Integer
- storm基础系列之一----storm并发度概念剖析
- 利用Jquery实现页面上div的拖动及位置保存
- Android--入门
- UVa 10054,欧拉回路
- Android ADB server didn&#39;t ACK * failed to start daemon * 简单有效的解决方案
- 8.3 MPI
- C++ STL 算法精选之查找篇
- 关于样式选择器:hover出现忽闪现象
- React——共享state
- Leetcode_128_Longest Consecutive Sequence
- php微信h5支付超简单!!!
- Vector的用法
- bzoj 泛做
- 解决采集知乎数据时由于账号被封遗漏的账号重爬问题(python代码)
- BZOJ 1977[BeiJing2010组队]次小生成树 Tree - 生成树
- [Winform]默认以管理员身份运行程序
- 声卡由于其配置信息(注册表中的)不完整或已损坏,Windows 无法启动这个硬件设备。(代码 19),
- docker 指令