力扣(LeetCode)652

66次阅读

共计 1193 个字符,预计需要花费 3 分钟才能阅读完成。

题目地址:https://leetcode-cn.com/probl… 题目描述:给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1:
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树:
2
/
4

4
因此,你需要以列表的形式返回上述重复子树的根结点。
解答:如何判断两棵树是重复的?只要两棵树的先序 (各种序都可以) 遍历结果是一样的,那么这两棵树就是重复的?不一定!!!
2
/
4
和 2 \ 4 它们的先序遍历结果就是相同的,但是并不重复。为什么?因为遍历的时候忽略掉了空树的位置。但是如果先序访问这个树的时候保留空树 (也就是访问空树),那么此时就成立了!先序遍历树并且对它进行序列化,空树的序列化结果为 ” “,而对于任意节点 root 它的序列化结果为 ”root.val 左子树序列化 右子树序列化 ”。这里再用 hashmap 存储,键:序列化结果,值:树节点组成的链表。最后序列化完,遍历这个 hashmap,找到 hashmap 中,值(链表) 长度大于 1 的位置,把这个位置链表的第一个节点放入答案集,按照这个思路就能理解下面的代码:java ac 代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {val = x;}
* }
*/
class Solution {
HashMap<String,List<TreeNode>> map = new HashMap(1000);

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
serialize(root);
List<TreeNode> ans = new ArrayList(1000);
for(Map.Entry<String,List<TreeNode>> entry:map.entrySet())
if(entry.getValue().size()>1)
ans.add(entry.getValue().get(0) );
return ans;
}

public String serialize(TreeNode root)
{
if(root == null)return ” “;
String temp = root.val+” “+serialize(root.left)+” “+serialize(root.right);
if(map.get(temp) == null){
List<TreeNode> list = new LinkedList();
list.add(root);
map.put(temp,list);
}
else map.get(temp).add(root);
return temp;
}

}

正文完
 0