1.题目描述
给定一棵二叉树 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]]
2.解题思路与代码
2.1 解题思路
这道题需要找到重复的子树， 我们使用 DFS 进行二叉树遍历，并且在遍历的同时对遍历的路径进行序列化成字符串，节点间用符号 “-” 进行分割。同时，我们使用一个 HashMap 来存放路径及该路径出现的次数。在对每个节点进行左右子节点遍历完成后，表示当前节点的子树路径已经序列化成了字符串，这个时候将路径放入 HashMap 中，并且路径计数加 1 。放入 HashMap 之后，这个时候需要判断 HashMap 中对应路径的数量是否为 2 ，如果为 2 则将当前节点放入结果列表中，由于子树存在重复的情况，如果仅仅判断路径是否存在则会导致重复统计，因此这里只判断是否为 2。从根节点开始 DFS 完成上面操作，最后返回结果列表即可。
2.2 代码
class Solution {
List<TreeNode> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
process(root);
return ans;
}
public String process(TreeNode node) {
if (node == null) {
return "-";
}
StringBuilder builder = new StringBuilder(String.valueOf(node.val));
builder.append("-");
String left = process(node.left);
String right = process(node.right);
builder.append(left).append(right);
map.put(builder.toString(), map.getOrDefault(builder.toString(), 0) + 1);
if (map.get(builder.toString()) == 2) {
ans.add(node);
}
return builder.toString();
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 使用深度优先对二叉树进行遍历，并且在遍历时对节点路径进行序列化
- 使用哈希表来存放节点的路径及改路径出现的次数
