寻找重复的子树
# 📃 题目描述
题目链接:
这题华为机考(2022.3.30 号)考过,原题
给定一棵二叉树 root,返回所有重复的子树。
对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值,则它们是重复的。
示例 1:
输入:root = [1,2,3,4,null,2,4,null,null,4]
输出:[[2,4],[4]]
# 🔔 解题思路
当出现需要判断是否重复时,需要想到使用 Map,key为二叉树的遍历结果(使用序列化的方式,将数据打平),value为对应该遍历结果出现的频率。
使用后序遍历,先获取左子树,然后再获取右子树,将本子树序列化,然后存储到 map中,如果出现频率出现 2 次,就表示出现重复子树
class Solution {
// key: 子树结构 value: 该结构出现的次数
private Map<String, Integer> map = new HashMap<>();
// 存储重复子树的根节点
private List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
if (root == null) {
return res;
}
serialize(root);
// 返回的是重复子树的根结点(多个)
return res;
}
// 序列化(后序遍历和先序遍历都行,唯独中序遍历不行)以当前节点为根节点的二叉树
private String serialize(TreeNode root) {
if (root == null) {
return "null";
}
// 后序遍历
String str1 = serialize(root.left);
String str2 = serialize(root.right);
String str = str1 + "," + str2 + "," + root.val;
// 更新 map
map.put(str, map.getOrDefault(str, 0) + 1);
// 重复子树,加入 res
if (map.get(str) == 2) {
res.add(root);
}
return str;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10