LeetCode652：查找重复子树查找重复子树题目：给定一棵二叉树，返回所有重复子树。对于相同类型的重复子树，只需要返回其中任一子树的根节点即可。当两棵树具有相同的结构和相同的节点值时，它们被复制。给定一棵二叉树，返回所有重复的子树。对于每一种重复的子树，只需要返回其中任何一棵的根节点。如果两棵树具有相同的结构且节点值相同，则它们是重复的。例1：1/\23//\424/4这里有两棵重复的子树：2/4和4所以，需要以列表的形式返回上述重复子树的根节点。因此，您需要以列表的形式返回上面树的根。解题思路：这是一道考察二叉树遍历的题。遍历时，将其序列化为String类型，存储到Map中。如果是第二次出现，就会将该节点添加到数组中。代码：这是一个后序遍历的例子。需要注意的是，叶节点应该指定一个特殊的字符来代替空节点。Hereis'#'Java:classSolution{publicListfindDuplicateSubtrees(TreeNoderoot){Listlist=newArrayList<>();//返回的数组if(root==null)returnlist;Mapmap=newHashMap<>();//ha希望映射找到重复的子节点traverse(root,map,list,"");返回列表；}//后序遍历privateStringtraverse(TreeNodenode,Mapmap,Listlist,Stringtree){if(node==null)returntree+"#";Stringleft=traverse(node.left,map,list,tree);//递归左子Stringright=traverse(node.right,map,list,tree);//递归右子tree=tree+node.val+left+right;//每个子树路径map.put(tree,map.getOrDefault(tree,0)+1);//存储每个子树路径if(map.get(tree)==2)list.add(node);//存储相同路径第二次出现时的节点returntree;}}Python:classSolution:deffindDuplicateSubtrees(self,root:TreeNode)->List[TreeNode]:res=[]#arraytobereturnedifnotroot:returnreshash_map={}#hashmap查找重复的子节点self.traverse(root,hash_map,res,'')returnres#后序遍历deftraverse(self,node:TreeNode,hash_map,res,tree):ifnotnode:returntree+'#'left=self.traverse(node.left,hash_map,res,tree)#递归左子childright=self.traverse(node.right,hash_map,res,tree)#递归右子childtree=tree+str(node.val)+left+right#每个子树路径iftreeinhash_map.keys():#存储每个子树路径hash_map[tree]+=1else:hash_map[tree]=1ifhash_map[tree]==2:#存储节点时第二次出现相同的路径res.append(node)returntree欢迎关注微信公众号：爱写bug
